質問: pythonを最近学習し始めた者です。 pythonを使用してやりたいことがあるのですが、キーワードがわからない為、やり方を検索できずにいます。 以下やりたい内容となります。 やりたいこと:ある地域の中に3つのタクシー会社があるとします。(会社A・会社B・会社C)各会社の所有タクシー数は、[会社A:2台][会社B:2台][会社C:1台] タクシーを呼ぶ人は地域内の建物にいることとし、タクシー会社から地域内の各建物までの距離はあらかじめ別のcsvファイルで作成してあります。 タクシーを呼ぶ人がいた時、タクシーを呼んだ人がいる建物に近い会社からタクシーを配車させることを繰り返した時に、タクシーがすべて出払っている会社が出るといった事象が起きることが考えられますが、そういった場合に、タクシーを呼んだ人のいる建物から近く、タクシーの残っている会社からタクシーを配車する場合にはpythonのどのような機能を使用すればよいでしょうか。 3つの会社のタクシー数<タクシーを呼ぶ人の数 とし、全タクシー会社のタクシーがすべて配車されるまで繰り返すものとします。 このような内容をpythonで構築したい場合、どのようなキーワードで検索、どのような構文で構築するのが良いのでしょうか。 初歩的なことをお聞きし申し訳ございませんが、よろしくお願いいたします。
回答: アルゴリズムとしては、貪欲法で配車問題を解きたいという話だと感じました。 具体的には、次のように問題を抽象化して: ``` resource[i] : 会社 i の所有タクシー数 cost[i][j] : 建物 i から会社 j までの距離 jobs[i] : i 番目の呼び出しで呼ばれた先の建物 ``` これに対し「タクシーが残っている会社 (`cost[i][j] > 0` な会社 `j`) の中で距離が最短の会社 (`cost[job[i]][j]` が最小の会社 `j`) 」を順番に割り当てていく手順です。 疑似的にプログラムを書くとこのような感じです: ``` result = [-1] * len(jobs) for i, job in enumerate(jobs): # 最短の会社を見つける nearest = -1 min_cost = float("inf") for company, r in enumerate(resource): if r > 0 and cost[job][company] < min_cost: nearest = company min_cost = cost[job][company] if nearest == -1: # もうタクシーが残っていない break # 見つけた会社に割り振る resource[nearest] -= 1 result[i] = nearest ```