21.06.2013, 00:20
|
 |
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,126
|
|
|
Hekumok, начинаем с 0,0
тупой перебор всех точек до которой короче - её запоминаем - записываем растояние -- запомненную точку убираем из массива -- ищем до какой короче ... и т.д.
|
|
21.06.2013, 00:33
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,126
|
|
Hekumok, мой вариант
<!DOCTYPE html>
<html>
<head>
<title>Untitled</title>
</head>
<body>
<script>
var a = [[94,163], [14,58], [50,40], [14,103], [10,10], [74,58], [54,163], [94,103], [50,10], [74,40]];
var Lmin = 0,
n = 0,
f = [[0, 0]],
N = a.length;
for (var i = 0; i < N; i++) {
var c = a[0][0] - f[0][0],
d = a[0][1] - f[0][1],
temp = Math.sqrt(c * c + d * d);
for (var j = 1; j < a.length; j++) {
c = a[j][0] - f[0][0],
d = a[j][1] - f[0][1];
if (Math.sqrt(c * c + d * d) < temp) {
temp = Math.sqrt(c * c + d * d);
n = j
}
}
document.write(f + "<br>" + temp + "<br>")
Lmin += temp
f = a.splice(n, 1);
n = 0;
}
document.write(f + "<br>" + Math.round(Lmin))
</script>
</body>
</html>
Последний раз редактировалось рони, 21.06.2013 в 00:35.
|
|
21.06.2013, 00:37
|
 |
✔
|
|
Регистрация: 04.06.2012
Сообщений: 513
|
|
рони, понял, спасибо 
__________________
★ ²º¹³ ☆
|
|
21.06.2013, 02:07
|
|
✔
|
|
Регистрация: 04.06.2012
Сообщений: 513
|
|
|
Дзен-трансгуманист, спасибо за ссылки)
рони, вашим способом получается 406(
__________________
★ ²º¹³ ☆
|
|
21.06.2013, 02:19
|
|
без статуса
|
|
Регистрация: 25.05.2012
Сообщений: 8,219
|
|
|
Hekumok,
Про деревья вроде кратчайший путь,(если круговой с возвратом к калитке), по вершинам многоугольника максимально близкого к выпуклому
|
|
21.06.2013, 02:28
|
|
✔
|
|
Регистрация: 04.06.2012
Сообщений: 513
|
|
Deff, я чё-т не представляю, как это сделать 
__________________
★ ²º¹³ ☆
|
|
21.06.2013, 03:30
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,126
|
|
|
Сообщение от Hekumok
|
|
вашим способом получается 406
|
это как? |
|
21.06.2013, 03:40
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,126
|
|
Вариант с возвратом на 10 пар, алгоритм тотже ближайший сосед
маршрут выбран в результате
[[0,0],[50,10],[50,40],[74,40],[74,58],[94,103],[94,163],[54,163],[14,103],[14,58],[10,10],[0,0]]
немного походит на
|
Сообщение от Deff
|
|
по вершинам многоугольника максимально близкого к выпуклому
|
результат 452
var a = [[94,163], [14,58], [50,40], [14,103], [10,10], [74,58], [54,163], [94,103], [50,10], [74,40]];
var Lmin = 0,
n = 0,
f = [[0, 0]],ff = [[0,0]],
N = a.length;
for (var i = 0; i < 5; i++) {
var c = a[0][0] - f[0][0],
d = a[0][1] - f[0][1],
temp = Math.sqrt(c * c + d * d);
for (var j = 1; j < a.length; j++) {
c = a[j][0] - f[0][0],
d = a[j][1] - f[0][1];
if (Math.sqrt(c * c + d * d) < temp) {
temp = Math.sqrt(c * c + d * d);
n = j
}
}
Lmin += temp
f = a.splice(n, 1);
n = 0;
var c = a[0][0] - ff[0][0],
d = a[0][1] - ff[0][1],
temp = Math.sqrt(c * c + d * d);
for (var j = 1; j < a.length; j++) {
c = a[j][0] - ff[0][0],
d = a[j][1] - ff[0][1];
if (Math.sqrt(c * c + d * d) < temp) {
temp = Math.sqrt(c * c + d * d);
n = j
}
}
Lmin += temp
ff = a.splice(n, 1);
n = 0;
}
c = f[0][0] - ff[0][0],
d = f[0][1] - ff[0][1];
temp = Math.sqrt(c * c + d * d);
Lmin += temp
alert(Math.round(Lmin))
|
|
21.06.2013, 05:10
|
|
без статуса
|
|
Регистрация: 25.05.2012
Сообщений: 8,219
|
|
|
Сообщение от рони
|
|
результат 452
|
Для анализа действий желательно для начала построить картинку - карту точек |
|
21.06.2013, 08:45
|
|
✔
|
|
Регистрация: 04.06.2012
Сообщений: 513
|
|
|
Сообщение от рони
|
|
это как?
|
Ну, вашим способом + возврат в [0, 0]
__________________
★ ²º¹³ ☆
|
|
|
|
