質問編集履歴
3
文章の修正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -4,7 +4,9 @@
|
|
|
4
4
|
|
|
5
5
|
Javaで山登り法を用いて，２つの都市を入れ替え続けるソースコードを書きました．最終的にツアーの経路がより短い物を選ぶというものです．
|
|
6
6
|
|
|
7
|
-
エラーメッセージは出ていないのですが，毎回ランダムの乱数を作っているはずなのに，同じベストスコア5.0と文字化けのような文字が出ます．
|
|
7
|
+
エラーメッセージは出ていないのですが，毎回ランダムの乱数を作っているはずなのに，同じベストスコア5.0と文字化けのような文字が出ます．
|
|
8
|
+
|
|
9
|
+
HillClimbingクラスのmain文をどう書けばいいのかが分かりません．
|
|
8
10
|
|
|
9
11
|
|
|
10
12
|
|
2
TSPStateクラスを追加しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -310,10 +310,178 @@
|
|
|
310
310
|
|
|
311
311
|
|
|
312
312
|
|
|
313
|
+
|
|
314
|
+
|
|
313
315
|
package tsp;
|
|
314
316
|
|
|
315
317
|
|
|
316
318
|
|
|
319
|
+
import java.util.ArrayList;
|
|
320
|
+
|
|
321
|
+
import java.util.Collections;
|
|
322
|
+
|
|
323
|
+
import java.util.List;
|
|
324
|
+
|
|
325
|
+
|
|
326
|
+
|
|
327
|
+
public class TSPState {
|
|
328
|
+
|
|
329
|
+
private final ArrayList<Point> points;
|
|
330
|
+
|
|
331
|
+
private boolean scoreCalculated = false;
|
|
332
|
+
|
|
333
|
+
private double score;
|
|
334
|
+
|
|
335
|
+
|
|
336
|
+
|
|
337
|
+
public TSPState(List<Point> points) {
|
|
338
|
+
|
|
339
|
+
this.points = new ArrayList<Point>(points);
|
|
340
|
+
|
|
341
|
+
this.scoreCalculated = false;
|
|
342
|
+
|
|
343
|
+
this.score = 0;
|
|
344
|
+
|
|
345
|
+
}
|
|
346
|
+
|
|
347
|
+
|
|
348
|
+
|
|
349
|
+
public TSPState(TSPState s) {
|
|
350
|
+
|
|
351
|
+
this.points = new ArrayList<Point>(s.getPoints());
|
|
352
|
+
|
|
353
|
+
this.scoreCalculated = s.scoreCalculated;
|
|
354
|
+
|
|
355
|
+
this.score = s.score;
|
|
356
|
+
|
|
357
|
+
}
|
|
358
|
+
|
|
359
|
+
|
|
360
|
+
|
|
361
|
+
public int size() {
|
|
362
|
+
|
|
363
|
+
return points.size();
|
|
364
|
+
|
|
365
|
+
}
|
|
366
|
+
|
|
367
|
+
|
|
368
|
+
|
|
369
|
+
public List<Point> getPoints() {
|
|
370
|
+
|
|
371
|
+
return Collections.unmodifiableList(points);
|
|
372
|
+
|
|
373
|
+
}
|
|
374
|
+
|
|
375
|
+
|
|
376
|
+
|
|
377
|
+
public List<Point> getMutablePoints() {
|
|
378
|
+
|
|
379
|
+
scoreCalculated = false;
|
|
380
|
+
|
|
381
|
+
return points;
|
|
382
|
+
|
|
383
|
+
}
|
|
384
|
+
|
|
385
|
+
|
|
386
|
+
|
|
387
|
+
public double getScore() {
|
|
388
|
+
|
|
389
|
+
if (!scoreCalculated) {
|
|
390
|
+
|
|
391
|
+
score = calculateScore();
|
|
392
|
+
|
|
393
|
+
scoreCalculated = true;
|
|
394
|
+
|
|
395
|
+
}
|
|
396
|
+
|
|
397
|
+
|
|
398
|
+
|
|
399
|
+
return score;
|
|
400
|
+
|
|
401
|
+
}
|
|
402
|
+
|
|
403
|
+
|
|
404
|
+
|
|
405
|
+
private double calculateScore() {
|
|
406
|
+
|
|
407
|
+
if (points.size() <= 1)
|
|
408
|
+
|
|
409
|
+
return 0;
|
|
410
|
+
|
|
411
|
+
|
|
412
|
+
|
|
413
|
+
double sumDistance = 0;
|
|
414
|
+
|
|
415
|
+
for (int i = 1; i < points.size(); ++i) {
|
|
416
|
+
|
|
417
|
+
Point p1 = points.get(i - 1);
|
|
418
|
+
|
|
419
|
+
Point p2 = points.get(i);
|
|
420
|
+
|
|
421
|
+
|
|
422
|
+
|
|
423
|
+
sumDistance += p1.attDistance(p2);
|
|
424
|
+
|
|
425
|
+
}
|
|
426
|
+
|
|
427
|
+
|
|
428
|
+
|
|
429
|
+
sumDistance +=
|
|
430
|
+
|
|
431
|
+
points.get(0).attDistance(points.get(points.size() - 1));
|
|
432
|
+
|
|
433
|
+
return sumDistance;
|
|
434
|
+
|
|
435
|
+
|
|
436
|
+
|
|
437
|
+
}
|
|
438
|
+
|
|
439
|
+
|
|
440
|
+
|
|
441
|
+
// 点P_1とP_jの距離を返す
|
|
442
|
+
|
|
443
|
+
public double distance(int i, int j) {
|
|
444
|
+
|
|
445
|
+
Point p1 = points.get(i % points.size());
|
|
446
|
+
|
|
447
|
+
Point p2 = points.get(j % points.size());
|
|
448
|
+
|
|
449
|
+
return p1.attDistance(p2);
|
|
450
|
+
|
|
451
|
+
}
|
|
452
|
+
|
|
453
|
+
|
|
454
|
+
|
|
455
|
+
// 点Pi, Pjを入れ替える
|
|
456
|
+
|
|
457
|
+
public void swap(int i, int j) {
|
|
458
|
+
|
|
459
|
+
Point p = points.get(i);
|
|
460
|
+
|
|
461
|
+
points.set(i, points.get(j));
|
|
462
|
+
|
|
463
|
+
points.set(j, p);
|
|
464
|
+
|
|
465
|
+
|
|
466
|
+
|
|
467
|
+
scoreCalculated = false;
|
|
468
|
+
|
|
469
|
+
}
|
|
470
|
+
|
|
471
|
+
|
|
472
|
+
|
|
473
|
+
|
|
474
|
+
|
|
475
|
+
}
|
|
476
|
+
|
|
477
|
+
|
|
478
|
+
|
|
479
|
+
|
|
480
|
+
|
|
481
|
+
package tsp;
|
|
482
|
+
|
|
483
|
+
|
|
484
|
+
|
|
317
485
|
public interface TSPSolver {
|
|
318
486
|
|
|
319
487
|
// 現在の状態集合の中で最もよいものを得る。１つしかなければそれを返す。
|
1
AbstractTSPSolverクラスのインターフェイスTSPSolverを追加しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -314,6 +314,26 @@
|
|
|
314
314
|
|
|
315
315
|
|
|
316
316
|
|
|
317
|
+
public interface TSPSolver {
|
|
318
|
+
|
|
319
|
+
// 現在の状態集合の中で最もよいものを得る。１つしかなければそれを返す。
|
|
320
|
+
|
|
321
|
+
public TSPState getBestState();
|
|
322
|
+
|
|
323
|
+
|
|
324
|
+
|
|
325
|
+
// 計算を 1step 進める
|
|
326
|
+
|
|
327
|
+
public abstract boolean step();
|
|
328
|
+
|
|
329
|
+
}
|
|
330
|
+
|
|
331
|
+
|
|
332
|
+
|
|
333
|
+
package tsp;
|
|
334
|
+
|
|
335
|
+
|
|
336
|
+
|
|
317
337
|
public class Point {
|
|
318
338
|
|
|
319
339
|
public double x, y;
|