Вычислить оптимальный маршрут для выбора ресурсов - PullRequest
Новая
       6

Вычислить оптимальный маршрут для выбора ресурсов

0 голосов
/ 27 ноября 2018

Вот правила (Halite 3):

На каждом ходу вы должны принять одно решение для своего корабля.Вы можете двигаться вправо, двигаться влево, двигаться вверх, двигаться вниз или оставаться на месте (и собирать ресурсы).

Перемещение вашего корабля обойдется вашему кораблю в 10% от имеющихся ресурсов текущего ячейки.Пребывание на месте ничего не стоит вам, и вы выбираете 25% текущих доступных ресурсов.Если у корабля нет ресурсов, чтобы заплатить 10% за ход, он прикреплен к клетке на этот ход (не может быть отрицательным).

Моя цель: корабль начинается в центре (0) и должен вернуться в этот момент, по крайней мере (X количество ресурсов) в меньшем возможном повороте.

Как я могу рассчитать наиболее эффективный путь (по кругу), который должен пройти мой корабль для достижения моей цели?

Вот некоторый код для вычисления случайной карты (карта случайна в каждой игре): 

import random

how_Big = 11 
center_Pos = int(how_Big/2) #how_Big must be even

game_Map = [[random.randint(1,500) for i in range(how_Big)] for x in range(how_Big)]
game_Map[center_Pos][center_Pos] = 0

for y in range(how_Big):
    print(game_Map[y])

[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 479, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 172, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]

Я не совсем уверен, как начать.Есть какой-нибудь известный алгоритм для этого?

Спасибо

Дополнительная информация:

  • Матрица - это доступные ресурсы в начале каждой ячейки.
  • Корабль начинается с 0 ресурсов.
  • Корабль получает ресурсы, оставаясь неподвижным в течение раунда в клетке (собирая 25% ресурсов клетки).
  • Корабль тратит ресурсы (своего груза), перемещаясь (стоимость 10% доступных ресурсов текущей ячейки).
  • Путь может быть возвращен в любом случае, например (move = ["up", "still", "still", "up", "still", "still", "глубоко вниз"]).BruteForce это будет приемлемо.
  • X будет минимальной суммой, которую я хочу, чтобы груз моего корабля имел при возвращении в центр.
  • Карта всегда имеет центр Ячейка
  • Собранные ресурсыили используется всегда округляется до ближайшего Int
  • Ресурсы, собранные кораблем, удаляются из ячейки

Вот пример того, что может произойти: 

move_Dict = {
    "up": [-1, 0],
    "down": [1, 0],
    "right": [0, 1],
    "left": [0, -1],
    "still": [0, 0],
}

moves = ["up", "still", "still", "up", "still", "still", "down", "down"]
position = [5, 5]
cargo = 0

print("initial map :")
for y in range(how_Big):
        print(game_Map[y])

for move in moves:
    if move == "still":
        ressources_Collected = round(game_Map[position[0]][position[1]] * 0.25)
        cargo += ressources_Collected
        game_Map[position[0]][position[1]] -= ressources_Collected
    else:
        ressources_Used = round(game_Map[position[0]][position[1]] * 0.10)
        cargo -= ressources_Used
        position = [position[0]+move_Dict[move][0], position[1]+move_Dict[move][1]]

    print(f"ship is at position {position}, cargo = {cargo}")
    for y in range(how_Big):
        print(game_Map[y])

Вывод: 

initial map :
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 479, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 172, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [4, 5], cargo = 0
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 479, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 172, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [4, 5], cargo = 43
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 479, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 129, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [4, 5], cargo = 75
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 479, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 97, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [3, 5], cargo = 65
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 479, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 97, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [3, 5], cargo = 185
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 359, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 97, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [3, 5], cargo = 275
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 269, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 97, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [4, 5], cargo = 248
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 269, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 97, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
ship is at position [5, 5], cargo = 238
[110, 179, 97, 467, 347, 336, 368, 298, 107, 84, 123]
[415, 86, 12, 75, 354, 74, 250, 221, 51, 254, 252]
[368, 235, 389, 1, 155, 186, 149, 135, 458, 243, 344]
[391, 480, 485, 358, 416, 269, 270, 354, 203, 436, 146]
[62, 132, 490, 33, 445, 97, 127, 274, 130, 77, 356]
[239, 11, 459, 245, 214, 0, 324, 162, 58, 394, 202]
[241, 395, 46, 78, 191, 384, 203, 191, 56, 474, 237]
[85, 480, 181, 98, 122, 482, 90, 351, 257, 266, 182]
[398, 125, 195, 423, 219, 290, 140, 166, 413, 499, 428]
[213, 367, 142, 471, 141, 407, 382, 229, 332, 455, 53]
[207, 12, 319, 54, 246, 274, 474, 312, 170, 374, 188]
[Finished in 0.1s]
...