задачка

[Mayor]

задачка

из какой области задачка затрудняюсь определить, нус начнем:

на шахматной доске размера 100000 на 100000 клеток, стоит n шашек ( 2<=n<=50), которые могут стоять на одной и той же клетке, их можно двигать вверх вниз вправо влево, что считается за 1 ход
найти: минимальное количество ходов за которое можно согнать от 2х до n шашек в 1 клетку:

примеры:
шашек 4
xpos: 1,1,2,3
ypos: 1,1,1,1

ответ 0,1,2 (первые 2 и так стоят на одной клетке, потом туда проще загнать 3ю, а последней 4ю)

шашек 5:
xpos: 1,7,3,11,12
ypos: 2,5,10,12,10

ответ 3,11,20,34 ( ближе всех стоят 4 и 5, далее к ним можно подогнать 2ю, потом 3ю, потом 1ю)

[Dimka]

Если шашки могут накладываться друг на друга и ходят по вертикали и горизонтали на одну клетку за ход, то всегда кратчайший путь между исходной и целевой позициями будет лежать на катетах прямоугольного треугольника, где позиции будут концами гипотенузы.

Суть задачи в нахождении такой комбинации путей, чтобы их совокупная длина была минимальной - т.е. задача на минисумму.

[Dimka]

Brute force решение:

Код: (Ruby)

class Point
 def initialize(x, y)
  @x = x
  @y = y
 end
 attr_reader :x, :y
end

def distance(point1, point2)
 dx = (point1.x - point2.x).abs
 dy = (point1.y - point2.y).abs
 return dx + dy
end

def calcDistances(points)
 result = Array.new
 for i in 0...points.size
  result[i] = Array.new
  point1 = points[i]
  for j in 0...points.size
   point2 = points[j]
   result[i][j] = distance(point1, point2)
  end
 end
 return result
end

def selectBest(distances, points)
 shortest = 1E+308
 best = nil
 for i in 0...distances.size
  length = 0
  for j in 0...distances[i].size
   length += distances[i][j]
  end
  if length < shortest then
   shortest = length
   best = i
  end
 end
 return points[best], distances[best], shortest
end

def solve(points)
 distances = calcDistances(points)
 center, paths, shortestLength = selectBest(distances, points)
 puts("Центральная: (" + center.x.to_s + ", " + center.y.to_s + ")")
 puts("Длины маршрутов каждой до центральной: " + paths.join(", "))
 puts("Общее число ходов: " + shortestLength.to_s)
end

solve([Point.new(1, 1), Point.new(1, 1), Point.new(2, 1), Point.new(3, 1)])
solve([Point.new(1, 2), Point.new(7, 5), Point.new(3, 10), Point.new(11, 12), Point.new(12, 10)])

результаты:

Код:

Центральная: (1, 1)
Длины маршрутов каждой до центральной: 0, 0, 1, 2
Общее число ходов: 3
Центральная: (3, 10)
Длины маршрутов каждой до центральной: 10, 9, 0, 10, 9
Общее число ходов: 38

[Dimka]

Mayor1, ты пробовал применить "жадный" алгоритм. А почему его?

[Dimka]

Во-первых, матрица расстояний симметрична относительно главной диагонали, и на этом можно сэкономить как по памяти, так и по количеству расчётов.

Во-вторых, решение выбирает центральной клеткой позицию одной из шашек. Есть мнение, что если выбирать какие-то другие клетки, то можно получить ещё более экономное решение, хотя количество расчётов при этом возрастёт.

[Dimka]

Ещё более хорошее решение можно получить:
1) посчитав среднюю точку для всех имеющихся, т.е. взяв среднее для всех x и среднее для всех y - (ax, ay);
2) найдя x, принадлежащий какой-либо шашке, ближайший к ax - cx;
3) найдя y, принадлежащий какой-либо шашке, ближайший к ay - cy;
4) в качестве центральной выбрать клетку в позиции (cx, cy).

Результаты:

Код:

Точки: (1, 1), (1, 1), (2, 1), (3, 1)
Первое решение
        Центральная: (1, 1)
        Длины маршрутов каждой до центральной: 0, 0, 1, 2
        Общее число ходов: 3
Второе решение
        Центральная: (2, 1)
        Длины маршрутов каждой до центральной: 1, 1, 0, 1
        Общее число ходов: 3

Точки: (1, 2), (7, 5), (3, 10), (11, 12), (12, 10)
Первое решение
        Центральная: (3, 10)
        Длины маршрутов каждой до центральной: 10, 9, 0, 10, 9
        Общее число ходов: 38
Второе решение
        Центральная: (7, 10)
        Длины маршрутов каждой до центральной: 14, 5, 4, 6, 5
        Общее число ходов: 34

Брать позицию (ax, ay) невыгодно, поскольку, если она не совпадает отдельно по x и y с какими либо шашками, это ухудшает решение на 1 или 2 хода из-за необходимости шашкам ходить углом, а не по прямой.

[Mayor]

Mayor1, ты пробовал применить "жадный" алгоритм. А почему его?

потому что, по условиям запрещено применять эвристический ( решение должно быть оптимальным )

хм боюсь что я недостаточно понятно сформулировал условия: у тебя код выдает всего 1 общее количество ходов, а должен выдавать массив для 2,3 ... всех шашек, иными словами вначале надо из множества всех данных шашек найти подмножества (размером от 2х до размера данного множества включительно) наиболее близкорасположенных шашек

по идее есть 2 пути:
взять клетку и отсортировать все шашки по принципу удаленности от нее, но это займет 10**10 клеток на 50*лог50 шашек

и как ты предложил: взять набор шашек и найти ближайшую ко всем им клетку, временая сложность: 2^50 набора шашек - что тоже неприемлимо

ограничение по памяти что то в районе гига, по времени около 2х минут

есть идеи как срезать количество комбинаций в каком нить из путей?

[Mayor]

еще пример приведу на всякий случай:

шашек 3:

1-1 10-2 2-2

ответ: 2,10

разбор: чтобы согнать 2 шашки выбираем 1 и 3 тк 2ю полюбому гнать дольше, для трех попросту ищем "центр тажести"

я еще попробовал вот какой алгоритм: находим центр тажести для всех шашек, считаем число ходов выкидываем наиболее удаленную, ищем новый центр считаем число ходов и так пока не дойдем до 1й шашки...

но как оказалось он валится вот на таких данных:

шашек 5:
1-1,2-2,10-1,10-2,10-3

[Dimka]

потому что, по условиям запрещено применять эвристический ( решение должно быть оптимальным )

Вот я и спросил "почему"? Если алгоритм известен, это ещё не значит, что его можно применять в любых задачах. Нужно обосновать.

хм боюсь что я недостаточно понятно сформулировал условия: у тебя код выдает всего 1 общее количество ходов, а должен выдавать массив для 2,3 ... всех шашек, иными словами вначале надо из множества всех данных шашек найти подмножества (размером от 2х до размера данного множества включительно) наиболее близкорасположенных шашек

В приведённом условии задачи этого нет. А зачем эти подмножества? Такие подмножества - элемент решения "жадным" алгоритмом. Если же это элемент условия задачи, то за базу можно взять алгоритм Прима-Краскала для поиска остовного дерева минимальной длины на графе. Он как раз "жадный".

и как ты предложил: взять набор шашек и найти ближайшую ко всем им клетку, временая сложность: 2^50 набора шашек - что тоже неприемлимо

Чего? Моё второе решение имеет сложность 2n - двухпроходное по массиву точек. А первое - n(n+1).

Лучше приведи условие задачи, как оно есть, а не как ты его сам пересказал.

1-1 10-2 2-2

ответ: 2,10

Мой ответ: центральная (2, 2), количество ходов 1, 8, 0, итого 9.

шашек 5:
1-1,2-2,10-1,10-2,10-3

Мой ответ: (10, 2), количество ходов: 10, 8, 1, 0, 1, итого 20.

[Mayor]

Вот я и спросил "почему"? Если алгоритм известен, это ещё не значит, что его можно применять в любых задачах. Нужно обосновать.

потому что решение должно быть оптимальным, если сушествует возможность меньшего количество ходов решение признается неверным и незащитывается

В приведённом условии задачи этого нет. А зачем эти подмножества? Такие подмножества - элемент решения "жадным" алгоритмом.

требуется найти минимальное количество ходов для числа шашек от 2х до N, ты упорно ищешь только для N

Мой ответ: центральная (2, 2), количество ходов 1, 8, 0, итого 9.

опять решил только для 4х когда перед\после этого нада было привести минимальное количество ходов для 2 и 3х из 4

Мой ответ: (10, 2), количество ходов: 10, 8, 1, 0, 1, итого 20.

опять решил только для 5х когда перед\после этого нада было привести минимальное количество ходов для 2 и 3х и 4х из 5

Лучше приведи условие задачи, как оно есть, а не как ты его сам пересказал.

N шашек размещены на бесконечно большой доске.  i шашка расположена в клетке  с координатами
x[i],y[i]. Может быть более одной шашки в одной и той же клетке. Ходы представляют собой движение на 1 клетку вверх, вниз, влево, вправо.
Нужно вернуть массив размером N-1, индексирование начинается с 0, в котором i элемент является минимальным количеством ходов необходимым, чтобы привести i+2 шашек в 1 и туже клетку.

[Dimka]

Нужно вернуть массив размером N-1, индексирование начинается с 0, в котором i элемент является минимальным количеством ходов необходимым, чтобы привести i+2 шашек в 1 и туже клетку.

Но тут не сказано, что на каждом шаге нужно использовать "достижение" предыдущего шага. Тут сказано, что нужно найти минимум для каждого подмножества шашек (надо полагать, шашки выбираются из множества произвольным образом).

[Mayor]

Нужно вернуть массив размером N-1, индексирование начинается с 0, в котором i элемент является минимальным количеством ходов необходимым, чтобы привести i+2 шашек в 1 и туже клетку.

Но тут не сказано, что на каждом шаге нужно использовать "достижение" предыдущего шага. Тут сказано, что нужно найти минимум для каждого подмножества шашек (надо полагать, шашки выбираются из множества произвольным образом).

если бы сказали, тогда бы задачка была слишком проста, но если подмножество шашек выбирать произвольным образом то задача будет не решаема для 50 шашек

[Dimka]

Mayor1, первая часть твоего утверждения противоречит второй. Если решение просто, то задача должна решаться, иначе либо решение не простое, либо это не решение.

"Произвольным" в моём понимании - это когда я сам решаю, какие шашки выбирать. Выбирать нужно такие шашки, которые в сумме дают минимальное количество ходов при своём перемещении по сравнению с другими равномощными подмножествами.

А алгоритм выбора по-моему не такой уж замысловатый.

[Mayor]

Mayor1, первая часть твоего утверждения противоречит второй. Если решение просто, то задача должна решаться, иначе либо решение не простое, либо это не решение.

ничего не противоречит, для фиксированого набора шашек, ты уже привел понятное и правильное  решение, теперь нада хотя бы теоретически доказать что задача решаема по временное сложности

"Произвольным" в моём понимании - это когда я сам решаю, какие шашки выбирать. Выбирать нужно такие шашки, которые в сумме дают минимальное количество ходов при своём перемещении по сравнению с другими равномощными подмножествами.
А алгоритм выбора по-моему не такой уж замысловатый.

не уверен, что алгоритм будет простой, возможно ваще что через перебор подмножеств не решить

в общем надо думать как отсечь большую часть вариантов

[Mayor]

все нашел:

вкратце повторюсь:
у нас есть множество шашек на практически бесконечной доске, нада найти центры тяжести с наименее удаленными шашками для подмножеств мощностью 2..N

для фиксированого подмножества шашек димка уже нашел решение, теперь остается 2 пути:

либо перебираем каждую клетку доски, проверяя ее как центр тяжести для подмношеств |2..N|
либо перебираем каждое подмножество шашек, исща его центр тяжести

как можно заметить, для каждого из вариантов временная сложность выполнения являются неприемлимыми, что делать со 2м я не знаю, но для первого можно отсеч большую часть клеток, доказав следующую теорему:

теорема:
как минимум для 1 из центров тяжести подмножества шашек,  справедливо: он лежит на пересечении ряда принадлежащего какой либо из шашек и строки принадлежащей какой либо из шашек( не обязательно той же)

доказательство:
тк движения по х и у ассоциативны, то взяв начальную координату так, что все шашки лежали бы по направлению движения, будем перемещаять центр сбора в сторону не увеличивающую число ходов для ее достижения, пока не найдем грани перехода с отрезка минимума фукнции на ее увеличение:

при переходе с клетки на клетку не принадлежащих координате шашек изменения знака производной функции быть не может тк изменение числа ходов будет минус число шашек которые лежат по направлению движения + число шашек которые лежат провтив направления движения центра сбора что отрицательно или == 0

при захождении на клетку принадлежащую координате шашки изменение числа ходов шашек может либо остаться == 0 либо продолжить уменьшаться

а вот при покидании клетки принадлежащей координате шашки число ходов может увлеличится если число шашек по направлению движения станет меньше числа против направления движения

таким образом одна из искомых координат центра тяжести принадленит, какой то из шашек, но так как опрерации движения по х и у ассоциативны, то тоже справедливо и для движения по другой оси

 тем не менее мне до сих пор не удалось доказать, что координаты одного из центров тяжести принадлежат какой то 1 шашке, но это уже не важно:

мы имеем перебор не более 50*50 позиций, к каждой из них применяется сортировка шашек по принципу удаленности это еще 50*лог50, с последующим запоминанием минимума ходов для каждого из подмножеств

итого:
временная сложность 50**3*лог50
памяти требуется число байт для запоминания координаты доски(4 байта хватит для досок порядка 4*10**9)*2(оси)*48(число искомых подмножествс мощьностью от 2х до 50)

[Dimka]

Что-то как-то не до конца расписано...

N^2 - это перебор позиций

потом для каждой нужно найти расстояния до всех шашек - N, итого уже N^3

отсортировать каждый массив по возрастанию расстояний - при быстрой сортировке N*ln(N), итого уже N^2*(N+N*ln(N))

получить нарастающие суммы количества ходов для первых 2-х, 3-х, и т.д. шашек - ещё N-1, итого N^2*(N+(N-1)+ln(N))

для каждого размера подмножества i от 2 до N выбрать среди N^2 массивов такой, где нарастающая сумма в позиции i минимальна. Поиск минимума - N^2 (по всем массивам), который нужно проделать (N-1) раз.

Итого N^2*(N+(N-1)+ln(N))+N^2*(N-1). Если не ошибся в преобразованиях, то будет N^2*(3*N+ln(N)-2). Для N=50 будет около 1 млн. операций.

[Dimka]

Решение

Код: (Javascript)

// JavaScript 1.6 движок Mozilla

function convertPointToString(point) {
 with(point)
  return "(" + String(x) + ", " + String(y) + ")"
}

function convertPointsToString(points) {
 var result = "";
 for(var i in points) {
  if(result != "")
   result += ", ";
  result += convertPointToString(points[i]);
 }
 return result;
}

function uniqueAdd(item, array) {
 if(array.indexOf(item) == -1)
  array.push(item);
 return array;
}

function createCenters(points) {
 var xs = new Array(), ys = new Array();
 for(var i in points)
  with(points[i]) {
   xs = uniqueAdd(x, xs);
   ys = uniqueAdd(y, ys);
  }
 var result = new Array();
 for(var i in xs)
  for(var j in ys)
   result.push({x:xs[i],y:ys[j]});
 return result;
}

function calculatePathLength(point1, point2) {
 return Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y);
}

function createPointsWithPathLengths(points, centers) {
 var result = new Array();
 for(var i in centers) {
  var center = centers[i];
  var pointsWithPathLengths = new Array();
  for(var j in points) {
   var point = points[j];
   pointsWithPathLengths.push(
    {point:point,pathLength:calculatePathLength(center, point)});
  }
  result.push({center:center,pointsWithPathLengths:pointsWithPathLengths});
 }
 return result;
}

function orderByPathLengthsForCenters(pointsWithPathLengths) {
 for(var i in pointsWithPathLengths)
  with(pointsWithPathLengths[i])
   pointsWithPathLengths.sort(
    function(item1, item2) {
     return item1.pathLength - item2.pathLength;
    });
 return pointsWithPathLengths;
}

function createCumulativePointsSubsets(pointsWithPathLengths) {
 var result = new Array();
 for(var i in pointsWithPathLengths)
  with(pointsWithPathLengths[i]) {
   var totalPathLength = 0;
   var pointsSubset = new Array(), cumulativePointsSubsets = new Array();
   for(var j in pointsWithPathLengths)
    with(pointsWithPathLengths[j]) {
     totalPathLength += pathLength;
     pointsSubset = (new Array(point)).concat(pointsSubset);
     if(pointsSubset.length > 1)
      result.push(
       {center:center,pointsSubset:pointsSubset,pathLength:totalPathLength});
    }
  }
 return result;
}

function selectMinPathLengthForSubsetSize(cumulativePointsSubsets) {
 var result = new Array();
 for(var i in cumulativePointsSubsets) {
   var item = cumulativePointsSubsets[i];
   var size = item.pointsSubset.length;
   if(result[size] == undefined)
    result[size] = item;
   else if(result[size].pathLength > item.pathLength)
    result[size] = item;
  }
 return result.map(
  function(item, index, array) {
   return item;
  });
}

function solve(points) {
 return selectMinPathLengthForSubsetSize(
         createCumulativePointsSubsets(
          orderByPathLengthsForCenters(
           createPointsWithPathLengths(points,
            createCenters(points)))));
}

function task(points) {
 print("Дано: " + convertPointsToString(points));
 solutions = solve(points);
 print("Ответ:");
 for(var i in solutions)
  with(solutions[i]) {
   print(
    convertPointsToString(pointsSubset) + " => " +
    convertPointToString(center) + ", " +
    String(pathLength));
  }
 print("");
}

task([{x:1,y:1}, {x:1,y:1}, {x:2,y:1}, {x:3,y:1}]);
task([{x:1,y:2}, {x:7,y:5}, {x:3,y:10}, {x:11,y:12}, {x:12,y:10}]);
task([{x:1,y:1}, {x:10,y:2}, {x:2,y:2}]);
task([{x:1,y:1}, {x:2,y:2}, {x:10,y:1}, {x:10,y:2}, {x:10,y:3}]);

Результаты:

Код:

Дано: (1, 1), (1, 1), (2, 1), (3, 1)
Ответ:
(1, 1), (1, 1) => (1, 1), 0
(2, 1), (1, 1), (1, 1) => (1, 1), 1
(3, 1), (2, 1), (1, 1), (1, 1) => (1, 1), 3

Дано: (1, 2), (7, 5), (3, 10), (11, 12), (12, 10)
Ответ:
(11, 12), (12, 10) => (11, 10), 3
(3, 10), (11, 12), (12, 10) => (11, 10), 11
(11, 12), (12, 10), (7, 5), (3, 10) => (7, 10), 20
(1, 2), (11, 12), (12, 10), (7, 5), (3, 10) => (7, 10), 34

Дано: (1, 1), (10, 2), (2, 2)
Ответ:
(2, 2), (1, 1) => (1, 1), 2
(10, 2), (1, 1), (2, 2) => (2, 2), 10

Дано: (1, 1), (2, 2), (10, 1), (10, 2), (10, 3)
Ответ:
(10, 2), (10, 1) => (10, 1), 1
(10, 3), (10, 1), (10, 2) => (10, 2), 2
(2, 2), (10, 3), (10, 1), (10, 2) => (10, 2), 10
(1, 1), (2, 2), (10, 3), (10, 1), (10, 2) => (10, 2), 20

Время работы и расход памяти на этих примерах неощутимые.