「騎士の巡回問題」のプログラムを作るには？

情けない学生 2004-07-21 09:51:51 No: 10012

新たにスレッドを立てます。
「騎士の巡回」のプログラムがまったくわからず、友人達と協力しても歯が立ちません。
どなたかソースを教えていただければ幸いです。

スタテツ 2004-07-21 10:25:46 No: 10013

「巡回問題」は面白そうなので挑戦してみます。
とりあえず問題の詳細を教えてください。
データフォーマットとかも知っておきたいです。

スタテツ 2004-07-21 11:55:25 No: 10014

こりゃ難題ですね…っていうか研究者レベル。
ギブアップです。
一応ググッって得たソースを紹介しておきます。
総当り(Delphi)
http://www.delphiforfun.org/Programs/traveling_salesman.htm
ニューロンネット使用（Java）ichinii氏日本語
http://www2.plala.or.jp/ichinii/index.html

にしの 2004-07-21 19:57:53 No: 10015

こういう、仕事に関係ないプログラム、好きです^^;
頭の体操になる(笑)

スタテツさん、これは巡回セールスマン問題ですよ。
複数ある都市を回る、最短ルートを探すやつですよね。

騎士巡回問題は、単純に総当たりでいいのでは？
# 他にアルゴリズムを知らない^^;

例えば、8x8・・・だとでかいので^^;5x5の盤を想定します。
騎士は、最大２つのマスを移動しますよね。横に１，縦に２とか。つまり、盤をはみ出さないように、以下のようなデータを用意します。

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
これで、開始地点を(2,2)として、移動パターンごとに試し、移動したら０以外の数値を入れて、０でなければ他の移動箇所を試す、という総当たりになります。

こんな感じ。
・盤面の大きさを定義
const
N = 5; // 5以上に解あり。ただ、６以上はめちゃ遅い^^;

・TForm1にButton1とMemo1をはる。
・TForm1のPrivateに、以下の変数と関数を宣言。

    board: array[0..N + 3, 0..N + 3] of integer;
    count: integer;
    ans: integer;

procedure Move(x, y: integer);
procedure printboard;

・Button1のOnClickイベントを定義

procedure TForm1.Button1Click(Sender: TObject);
var
  i, j: integer;
begin
  for i := 0 to N + 3 do
    for j := 0 to N + 3 do board[i, j] := 1;
      for i := 2 to N + 1 do
        for j := 2 to N + 1 do board[i, j] := 0;
  count := 0;
  ans := 0;
  Move(2, 2);
end;

自前の関数を定義。
procedure TForm1.Move(x, y: integer);
const
  dx: array[0..7] of integer=(2, 1,-1,-2,-2,-1, 1, 2);
  dy: array[0..7] of integer=(1, 2, 2, 1,-1,-2,-2,-1);
var
  i: integer;
begin
  if board[x, y] <> 0 then Exit; (* すでに訪れた *)
  Inc(count);
  board[x, y] := count;
  if count = N * N then
    printboard  (* 完成 *)
  else
    for i := 0 to 7 do Move(x + dx[i], y + dy[i]);
  board[x, y] := 0;
  Dec(count);
end;

procedure TForm1.printboard;
var
  i, j: integer;
  s: String;
begin
  Inc(ans);
  Editor1.Lines.Add(Format('解その%d', [ans]));
  for i := 2 to N + 1 do
  begin
    s := '';
    for j := 2 to N + 1 do s := s + Format('%3d', [board[i, j]]);
    Editor1.Lines.Add(s);
  end;
end;

参考は、「C言語によるアルゴリズム辞典」です。

ウォレス 2004-07-22 00:50:26 No: 10016

騎士巡回の問題は、
その次の分岐先（２手先）の可能分岐数が最も少ないところを選択していけば解が簡単に見つかるそうです。

上述のソースは全部の解を羅列できますが、とりあえず１種類だけすばやく求めるにはこのアルゴリズムを使ってください。
50ｘ50でも一瞬で求まります。

以下、長いですが・・・・
（再帰はわけがわからなくなるので使っていません）

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
const
  N = 50; // 5以上に解あり。
  dx: array[0..7] of integer=(2, 1,-1,-2,-2,-1, 1, 2);
  dy: array[0..7] of integer=(1, 2, 2, 1,-1,-2,-2,-1);

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private 宣言 }
    board: array[0..N + 3, 0..N + 3] of integer;
    count: integer;
    ans, Flag : integer;
    TestCount :Integer;
    Gx,Gy :Integer;
    procedure Move(x, y: integer);
    procedure Draw(x, y: integer);
    procedure Search(x, y: integer);
    procedure Test(x, y: integer);
  public
    { Public 宣言 }
  end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
i, j: integer;
t1,t2: Longint;
begin

  for i := 0 to N + 3 do
    for j := 0 to N + 3 do board[i, j] := 1;
      for i := 2 to N + 1 do
        for j := 2 to N + 1 do board[i, j] := 0;
  count := 0;
  Flag := 0;
  ans := 0;
  Gx:=2;Gy:=2;
  board[Gx, Gy] := 1;
  Move(Gx, Gy);

  t1 := GetTickCount;
  for i := 0 to N*N-2 do
  begin
    Search(Gx, Gy);
    Move(Gx, Gy);
  end;
  t2 := GetTickCount;

Memo1.Lines.add(FloattoStr((t2-t1)/1000)+'s');

end;

procedure TForm1.Move(x, y: integer);
begin
  Inc(count);
  board[x, y] := count;
  Draw(x, y);

end;

procedure TForm1.Search(x, y: integer);
var
i,j,min: integer;
TCTest :array[0..7] of integer;
begin

for j := 0 to 7 do
begin

      if board[x+ dx[j] , y+ dy[j] ] = 0 then //未訪なら
      begin                                   //分岐先範囲をチェック
        TestCount := 0;
        for i := 0 to 7 do
            Test(x + dx[i]+ dx[j],  y + dy[i]+ dy[j]);

        TCTest[j] := TestCount;              //分岐数を記憶
      end
      else
      begin
        TCTest[j] :=255;
      end;

end;

    min := 0;
    for i := 1 to 7 do                       //最も分岐数が少ないものを選ぶ
      if TCTest[min] > TCTest[i] then min :=i;

Gx:= x + dx[min];
Gy:= y + dy[min];

end;

procedure TForm1.Test(x, y: integer);
begin

if board[x , y ] = 0 then Inc(TestCount); (* 未訪 *)

end;

procedure TForm1.Draw(x, y: integer);
var
x1,y1,x2,y2,offset: Integer;

begin
  offset := round(50/N);
  y1 := round(x*200/N);
  x1 := round(y*200/N);
  y2 := round((x+1)*200/N);
  x2 := round((y+1)*200/N);

Form1.Canvas.Rectangle(x1,y1,x2,y2);
Form1.Canvas.TextOut(x1 + offset,y1 + offset,IntToStr(count));

end;

end.

にしの 2004-07-22 02:31:15 No: 10017

すばらしい。
早いです。
いろいろあるもんですね。
全解出力のアルゴリズムを、オートマトンを利用して作ってみたけれど効果無しでした^^;
状態遷移を記録するだけで出来そうな気もするんですが。

ウォレス 2004-07-23 04:53:18 No: 10018

アルゴリズムってプログラマ達のトリビアかも。
（トリビアよりは役に立ちますか・・）
「C言語による最新アルゴリズム事典」はバイブルです（＾＾）