新しく発言する EXIT インデックスへ
最短距離を求めるプログラム

  最短距離を求めるプログラム ななえ 2004/06/05 22:26:32 
  !このプログラムではまず最初に始点を決め(... 大久保 2004/06/06 00:05:18 
  探索途中の仮の最短コースを記録するための... 白石 和夫 2004/06/06 06:44:24 
  │└N個の点の座標を入力する部分は, 白石 和夫 2004/06/06 08:12:25 
  Nはいくつくらいまで想定すれば良いのでしょ...2004/06/09 15:12:06 
   └だいたい10個くらいです。よろしくお願いし... ななえ 2004/06/15 01:48:50 
    └並べ替えが大変でしたが一応できました。バ...2004/06/15 21:15:17 
     └一部消し忘れが在りました。2004/06/16 09:45:30 
      └すみません。間違いがありました。2004/06/17 21:05:41 

  最短距離を求めるプログラム ななえ 2004/06/05 22:26:32  ツリーへ

最短距離を求めるプログラム 返事を書く
ななえ 2004/06/05 22:26:32
はじめまして。
N個の点の座標を入力して一筆書きで各点を通り最初の点に最短距離で戻ってくるプログラムを作りたいのですが・・・
どなたか教えてください(>_<)

  !このプログラムではまず最初に始点を決め(... 大久保 2004/06/06 00:05:18  ツリーへ

Re: 最短距離を求めるプログラム 返事を書く
大久保 2004/06/06 00:05:18
!このプログラムではまず最初に始点を決め(赤い点)、そこから
!一番近い所にある点を結びます。つぎにその点から一番近い所にある点を結びます。
!それを繰り返して、{最後に始点と線をつなぎます}。
!なのでひょっとすると、{}部分のせいで最短コースが得られないかも知れません。
randomize
let n=20
dim px(n)
dim py(n)
dim D(n)
set window 0,1,0,1
for i=1 to n
let px(i)=rnd
let py(i)=rnd
if i=1 then set point color 4 else set point color 1
plot points:px(i),py(i)
next i
plot lines:px(1),py(1);

let d(1)=1
let nn=1
for j=1 to n
let distance=maxnum
for i=2 to n
if d(i)=1 then goto 100
let dis=sqr((px(nn)-px(i))^2+(py(nn)-py(i))^2)
if distance>dis then
let distance=dis
let nm=i
end if
100 next i
let d(nm)=1
let nn=nm
plot lines:px(nm),py(nm);
next j
plot lines:px(nm),py(nm);px(1),py(1)
end

  探索途中の仮の最短コースを記録するための... 白石 和夫 2004/06/06 06:44:24  ツリーへ

Re: 最短距離を求めるプログラム 返事を書く
白石 和夫 2004/06/06 06:44:24
探索途中の仮の最短コースを記録するための配列s(N)と仮の最短距離を記録する変数tと用意しておきます。
N個の点の順列をすべて生成して,各順列について距離の和を求め,その時点での最短ルートと最短距離を更新していきます。
順列すべてについて処理が終われば,その時点での最短ルートが本当の最短ルートです。
順列すべてを生成する方法は,何通りかありますが,初心者向きの方法を「数学とコンピュータ1」(森北出版)に解説してあるので参照してください。

  │└N個の点の座標を入力する部分は, 白石 和夫 2004/06/06 08:12:25  ツリーへ

Re: 探索途中の仮の最短コースを記録するための... 返事を書く
白石 和夫 2004/06/06 08:12:25
N個の点の座標を入力する部分は,
100 INPUT n
110 DIM x(n),y(n)
120 FOR i=1 TO n
130 GET POINT: x(i),y(i)
140 NEXT i
です。

  Nはいくつくらいまで想定すれば良いのでしょ...2004/06/09 15:12:06  ツリーへ

Re: 最短距離を求めるプログラム 返事を書く
2004/06/09 15:12:06
Nはいくつくらいまで想定すれば良いのでしょうか?
10個で36万以上の方法を計算することになって、
時間も掛かりますし難しくなりそうなのですが、Nの上限が決まっていれば考え易いのですが?

   └だいたい10個くらいです。よろしくお願いし... ななえ 2004/06/15 01:48:50  ツリーへ

Re: Nはいくつくらいまで想定すれば良いのでしょ... 返事を書く
ななえ 2004/06/15 01:48:50
だいたい10個くらいです。よろしくお願いします!

    └並べ替えが大変でしたが一応できました。バ...2004/06/15 21:15:17  ツリーへ

Re: だいたい10個くらいです。よろしくお願いし... 返事を書く
2004/06/15 21:15:17
並べ替えが大変でしたが一応できました。バグが在るかもしれません。

!*** N個の点を最短で結ぶプログラム ***
!  順$は2-9を順に並べ替えた文字列:順$(2)は計算に使う文字列
!  保存の必要に応じて順$(3),順$(4),・・・を作成
SET ECHO "OFF"

!点の入力
INPUT PROMPT "点の数(9以下)?":n
DIM x(n),y(n),順$(n),桁(9)
FOR i=1 TO n
  INPUT PROMPT "点の座標を入力 x,y": x(i),y(i)
  PRINT "n=";i;" ";x(i);",";y(i)
NEXT i

!最初の文字列 順$(1)を作成
LET 順$(1)="23456789"
LET 順$(1)=順$(1)(1:n-1)

LET N0=FACT(n-1)   !並べ替えの総数
LET 順$(2)=順$(1)
LET i=1

!全ての並べ替えで計算
DO WHILE i<=N0
  CALL 計算
  PRINT "1" & 順$(2) & "1",計   !並べ替えの表示
  CALL 次順
  LET i=i+1
LOOP

PRINT "答え  ";"1" & 順min$ & "1"
IF 順next$<>"" THEN PRINT "答え2 ";"1" & 順next$ & "1"

SUB 計算 !並べ替えた点を結ぶ線の計算
  LET 計=0
  LET k0=1
  FOR j=1 TO n-1
   LET k=VAL(順$(2)(j:j))
   LET 計=計+(x(k)-x(k0))^2+(y(k)-y(k0))^2
   LET k0=k
  NEXT j
  LET 計=計+(x(1)-x(k))^2+(y(1)-y(k))^2
  IF i=1 THEN
   LET 最短=計
   LET 順min$=順$(2)
  ELSE
   CALL 保存
  END IF
END SUB

SUB 保存
  LET 逆順$=""
  FOR c=(n-1) TO 1 STEP -1
   LET 逆順$=逆順$ & MID$(順$(2),c,1)
  NEXT c
  IF 計<最短 THEN
   LET 最短=計
   LET 順min$=順$(2)
  ELSEIF 計=最短 AND 逆順$<>順min$ THEN
   LET 順next$=順$(2)
  ELSE
  END IF
END SUB

SUB 次順
  IF MOD(i,2)<>0 THEN
   CALL 移動(2)
  ELSEIF MOD(i,40320)=0 THEN
   CALL 移動(9)
  ELSEIF MOD(i,5040)=0 THEN
   CALL 移動(8)
  ELSEIF MOD(i,720)=0 THEN
   CALL 移動(7)
  ELSEIF MOD(i,120)=0 THEN
   CALL 移動(6)
  ELSEIF MOD(i,24)=0 THEN
   CALL 移動(5)
  ELSEIF MOD(i,6)=0 THEN
   CALL 移動(4)
  ELSE
   CALL 移動(3)
  END IF
END SUB

SUB 移動(桁)
  IF 桁=2 THEN
   LET 順$(2)=MID$(順$(2),2,1) & MID$(順$(2),1,1) & MID$(順$(2),3,n-1)
  ELSEIF 順$(桁)="" THEN
   LET 順$(桁)=MID$(順$(1),桁,1) & MID$(順$(1),1,桁-1) & MID$(順$(1),桁+1,n-1)
   LET 順$(2)=順$(桁)
   LET c=3
   DO WHILE c<桁
     LET 順$(c)=順$(桁)
     LET c=c+1
   LOOP
  ELSE
   LET 順$(桁)=MID$(順$(桁),桁,1) & MID$(順$(桁),1,桁-1) & MID$(順$(桁),桁+1,n-1)
   LET 順$(2)=順$(桁)
   LET c=3
   DO WHILE c<桁
     LET 順$(c)=順$(桁)
     LET c=c+1
   LOOP
  END IF
END SUB

END

     └一部消し忘れが在りました。2004/06/16 09:45:30  ツリーへ

Re: 並べ替えが大変でしたが一応できました。バ... 返事を書く
2004/06/16 09:45:30
一部消し忘れが在りました。

!点の入力 の2行目最後の ,桁(9)
を消してください。

      └すみません。間違いがありました。2004/06/17 21:05:41  ツリーへ

Re: 一部消し忘れが在りました。 返事を書く
2004/06/17 21:05:41
すみません。間違いがありました。
SUB 計算 部分を差し替えてください。

SUB 計算 !並べ替えた点を結ぶ線の計算
LET 計=0
LET k0=1
FOR j=1 TO n-1
LET k=VAL(順$(2)(j:j))
LET 計=計+SQR((x(k)-x(k0))^2+(y(k)-y(k0))^2)
LET k0=k
NEXT j
LET 計=計+SQR((x(1)-x(k))^2+(y(1)-y(k))^2)
IF i=1 THEN
LET 最短=計
LET 順min$=順$(2)
ELSE
CALL 保存
END IF
END SUB


インデックスへ EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。