距離間の最小値の求め方

Question

場所の距離間を全通り求めてその中から最小のものを選択するプログラムを作成しているのですが、例えば４つの場所ABCD間の距離を要素としてあらわした場合、

  int kyori[4][4]={{0,1,2,4},
		   {1,0,3,5},
		   {2,3,0,6},
		   {4,5,6,0}};

のように設定したとして、kyori[0][1],kyori[0][2],kyori[0][3]からスタートし、全ての場所を回るように残りを巡り、足しあわせた時最小値となる道順を求めると考える。
これをすべての通り方について考えると

kyori[0][1]+kyori[1][2]+kyori[2][3]+kyori[3][0]
kyori[0][1]+kyori[1][3]+kyori[3][2]+kyori[2][0]
kyori[0][2]+kyori[2][1]+kyori[1][3]+kyori[3][0]
kyori[0][2]+kyori[2][3]+kyori[3][1]+kyori[1][0]
kyori[0][3]+kyori[3][1]+kyori[1][2]+kyori[2][0]
kyori[0][3]+kyori[3][2]+kyori[2][1]+kyori[1][0]

と表すことができるのですが場所の数を増やしてkyoriの要素（例えばkyori[5][5]やkyori[6][6]としてkyori[0][n]（n=1,2,...）からスタート）が変わっても対応できるようなプログラムはどのように作成すればよろしいでしょうか？

Answer 1

巡回セールスマン問題の力任せ探索を実際にプログラミングしたいとのこと。
どのようにとのことですので大筋をお示しします。

1. 以下のような関数を作ります。fと呼びます。

・引数は、(【まだ訪れていないノード番号の集合】, 【現在値ノード番号】, 【完了後に訪れるべきノード番号】)
・戻り値は、最短となる巡回路の(【ノード番号の並び】, 【その場合の道のり】)
2. その関数の処理はこうです。
・【まだ訪れていないノード番号の集合】が大きさ0なら、(【長さ0の数列】, 【現在ノードから完了後に訪れるべきノードまでの距離】)を返して終了です。
・そうでなければ、まだ訪れていない各ノード番号について、
・(【まだ訪れていないノード番号の集合からそのノード番号を取り除いたもの】, 【ノード番号】, 【完了後に訪れるべきノード番号】)でf自身を呼び出し、巡回路の長さと経路を得ます。現在値ノードから経路の先頭までの距離を道のりの長さに加えます。
・上記のうち、最も短いものを選んで(【経路の先頭に自分のノード番号を挿入した列】, 【道のり】)を返します。
3. すべてのノード番号について、(【全ノードからそのノードだけ除いた集合】, 【そのノード】, 【そのノード】)でfを呼び、その結果のうち最短の経路を回答します。

Answer 2

こんにちは。

n箇所を特定の1点から開始して全て巡回する組み合わせは、n-1個からn-1個取り出した順列を生成すれば良いですね。「順列 生成 c言語」で検索すると多数のアルゴリズムがでてきますので、枚挙アルゴリズムの方はそれらを参考にされて下さい。

次に可変長サイズのデータ表現は、色々考えられます。
よく用いられる方法は、１次元配列にマッピングしてしまうことです。
２次元の m x n 配列を1次元配列array[mn]にマッピングする場合、その (i, j)要素array[in+j]でアクセスできます。