Знаходжанне аптымальнага рашэння, якое зводзіць да мінімуму абмежаванні?

Назавем гэтую праблему праблему стропальшчык-птушка (на самай справе стропальшчык з'яўляецца аналагам сервера і птушкі на просьбу, але ў мяне быў нервовы зрыў, думаючы пра гэта, я змяніў іх у надзеі атрымаць іншую кропку гледжання!).

  • Ёсць камень кідальнікі (стропальшчыка) і B птушкі.
  • <Літый> У стропальшчыка не ў межах дыяпазону адзін аднаго.
  • Груза-захопныя раз можа забіць усіх птушак у межах бачнасці з адбівальнікам і будзе спажываць адзін стрэл і адзін раз блок

Я спрабую высветліць аптымальнае рашэнне, якое зводзіць да мінімуму час і колькасць здымкаў, якое патрабуецца, каб забіць птушак далі пэўны шаблон прыбыцця птушак. Дазвольце мне прывесці прыклад з абсалютнымі лічбамі: 3 стропальшчыкаў і 4 птушак.

        Time        1            2            3           4             5
Slinger
S1                B1, B2     B1, B2, B3       B4
S2                               B1         B1, B2      B3,B4     
S3                  B1         B3, B4                 B1,B2,B3,B4

і мае дадзеныя выглядаюць наступным чынам:

>> print t
[
  {
    1: {S1: [B1, B2], S2: [], S3: [B1]}, 
    2: {S1: [B1, B2, B3], S2: [B1], S3: [B3, B4]},
    3: {S1: [B4], S2: [B1,B2], S3: []},
    4: {S1: [], S2: [B3, B4], S3: [B1, B2, B3, B4]}
  }
]

Ёсць цэлы шэраг рашэнняў, я мог думаць (Sx пры Т = да вынікае, што стропальшчык Sx прымае стрэл падчас к):

  1. S1 at t=1, S1 at t=2, S1 at t=3 <- Cost: 3 shots + 3 time units = 6
  2. S1 at t=2, S1 at t=3 <- Cost: 2 shots + 3 time units = 5
  3. S1 at t=1, S3 at t=2 <- Cost: 2 shots + 2 time units = 4
  4. S3 at t=4 <- Cost: 1 shot + 4 time units = 5

Мне здаецца, што рашэнне <моцны> 3 з'яўляецца аптымальным у гэтым. Вядома, я зрабіў гэта ўручную (так што ёсць магчымасць, я, магчыма, прапусціў што-то), але я не магу думаць аб маштабуецца спосаб зрабіць гэта. Акрамя таго, я хвалююся, ёсць прыватныя выпадкі, таму што рашэнне аднаго шутэр можа змяніць рашэнне іншых, а таму, што ў мяне ёсць агульнае ўяўленне, можа быць, гэта не мае значэння.

Што такое хуткі і добры спосаб рашэння гэтай праблемы ў Python? Я з цяжкасцю прыдумляю з добрай структурай дадзеных, каб зрабіць гэта пакінуць у спакоі алгарытм, каб зрабіць гэта. Я маю на ўвазе выкарыстанне дынамічнага праграмавання, так як гэта, здаецца, уцягвае даследаванне прасторы станаў, але я трохі заблытаўся аб тым, як працягнуць. Любыя прапановы?

7
@mhum: Думаць больш аб гэтым, я маю на ўвазе, гэтая праблема на самай справе можа быць закадаваны ў мінімальны набор вечка, выдаляючы паняцце часу і прыклаўшы функцыю кошту для кожнага набору. Вядома, я не ўпэўнены, як кадзіраваць стропальшчык ў праблему, хоць. Ці ёсць у вас якія-небудзь прапановы па гэтаму падыходу?
дададзена аўтар Legend, крыніца
Да ведама: З толькі адзін перыяд часу, ваша задача эквівалентная Мінімальны набор вечка .
дададзена аўтар mhum, крыніца

3 адказы

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

У вас ёсць двухмерных мэтавая функцыя, так што можа быць шэраг кампрамісаў паміж стрэламі і часу. Вызначэнне мінімальнага колькасці кадраў для канкрэтнага тэрміну менавіта праблема камплект вечка (як mhum прапануе). Праблема камплект вечка NP-цяжкай і цяжка наблізіцца, але на практыцы, галін і межаў, выкарыстоўваючы дваісты кампазіцыі лінейнага праграмавання з'яўляецца дастаткова эфектыўным ў пошуку аптымальнай.

4
дададзена
+1 Дзякуй за падказку. Я не эксперт LP, але я стрэльнуць кадуецца праблему. Я напісаў гэта ў якасці каментара ў верхняй частцы, але я маю ў выглядзе выдалення паняцці часу і прыклаўшы функцыю кошту, а не да кожнага вочка. Аднак, як я ўжо казаў, я не зусім ясна, пра тое, як сфармуляваць.
дададзена аўтар Legend, крыніца

Я прапаную выкарыстоўваць растравыя выявы для стропальшчыкаў і птушак, г.зн.

S1 = B1 = 1, S2 = B2 = 2, S3 = B3 = 4, B4 = 8

Затым ўваходныя дадзеныя могуць быць запісаныя ў выглядзе

bird_data = [[3, 0, 1], [7, 1, 12], [8, 3, 0], [0, 12, 15]]

Функцыя кошту можа цяпер быць запісаная наступным чынам:

def cost(shots):
    hit = units = 0
    for show, shot in zip(bird_data, shots):
        units += 1
        for n, birds in enumerate(show):
            if shot & 1:
                units += 1
                hit |= birds
                if hit == 15: # all are hit
                    return units
            shot >>= 1
    return 99 # penalty when not all are hit

Зараз гэта лёгка знайсці аптымальныя здымкі шляхам вылічэнні мінімуму функцыі выдаткаў:

from itertools import product

shot_sequences = product(*([range(7)]*len(bird_data)))

print min((cost(shots), shots) for shots in shot_sequences)

гэтая друк

(4, (0, 5, 0, 0))

што азначае, што аптымальным з'яўляецца 4 адзінкі, калі S1 і S3 (5 = 1 + 4) пажар пры Т = 2. Вядома, ваша рашэнне таксама магчыма, дзе S1 спрацоўвае пры Т = 1 і S3 пры Т = 2, абодва маюць аднолькавую вартасць.

Аднак, паколькі алгарытм выкарыстоўвае грубую сілу, бегаючы па ўсіх магчымых паслядоўнасцях стрэл, толькі хутка і практычна здзяйсняльна, калі наборы дадзеных вельмі мала, як у вашым прыкладзе.

1
дададзена
+1 Дзякуй за гэта. Я не зусім упэўнены, што я разумею кадоўку, але я вазьму яшчэ адзін стрэл на яго. На першы погляд, гэта можа быць не ўяўляецца магчымым, паколькі ў маёй рэальнай праблемы, працягласць складае каля 10000, які я думаю, што падарве час працы.
дададзена аўтар Legend, крыніца

Я мяркую, што вы ведаеце ўсе нумары вы даеце ў прыкладзе, калі вы пачынаеце алгарытм, і не атрымаць t2 пасля заканчэння t1 і г.д.

Я таксама мяркую, два стропальшчыкаў можа страляць адразу, хоць гэта не мае вялікага значэння.

Пры першым выбары, вы можаце прысвоіць значэнне кожнага вочка, быўшы amountOfBirdsInCell часу.

Гэта дае вам дзве ячэйкі са значэннямі 1, будучы S1t1, S1t2, астатняе ніжэй.

Толькі падчас апошніх крывяных клетак у вашым рахунку, так што выбар самага раннім выдаліць на гэты час для наступнага раўнду, што робіць яго найбольш каштоўнае час. Гэта першы выбар.

Цяпер выдаліце ​​птушак, забітых у гэтым першы выбар з усіх клетак.

Паўтарыце працэс вызначэння значэння для астатніх клетак. У вашым прыкладзе, вочка S3t2 дасць высокі вынік, будучы 0.

Паўтараючы гэты працэс, вы атрымліваеце найбольш каштоўныя клеткі на самыя раннія часы.

Адзін важны біт ваш прыклад не распаўсюджваецца на: Калі ваш першы самы каштоўны выбар знаходзіцца ў t2, наступны самы каштоўны выбар можа быць у момант t1 або t2, так што вы павінны прымаць да ўвагі тыя. Аднак, паколькі t2 ўжо пацверджаны, вы не павінны заняць свой час пад увагу іх кошт.

Я ніколі не пісаў у пітонаў, я тут з-за алгарытм тэга, так вось некаторыя Java/C-падобны псевдокод:

highestCellTime = 0;
while(birdsRemain)
{
    bestCell;

    for(every cell that has not been picked yet)
    {
        currentCellValue = amountOfBirds;
        if(currentCellTime > highestCellTime)
        {
            currentCellValue = currentCellValue - currentCellTime;
        }

        if(currentCellValue < bestCellValue)
        {
            bestCell = thisCell;
        }
        else if(currentCellValue == bestCellValue && currentCellTime < bestCellTime)
        {
            bestCell = thisCell;
        }
    }
    addCellToPicks(bestCell);
    removeBirdsFromOtherCells(bestCellBirds);
}

Калі я не забыўся нешта, зараз у вас ёсць аптымальнае спалучэнне клетак у вашай калекцыі кірхі.

Я спадзяюся, што гэты код мае сэнс пітон праграміст. Калі хто-то можа перавесці яго, калі ласка! І, калі ласка, выдаліце ​​гэты фрагмент тэксту і раней згадка пра Java/C-псевдокоде, калі вы робіце.

EDIT by OP: First version and does not end up with the best cells. I am guessing it must be a bug in my code but nevertheless I am posting here.

import math

cellsNotPicked = range(0,12)
cellToBird = {
    0: [1, 2],
    1: [],
    2: [1],
    3: [1,2,3],
    4: [1],
    5: [3,4],
    6: [4],
    7: [1,2],
    8: [],
    9: [],
    10: [3,4],
    11: [1,2,3,4]
}

picks = []

def getCellValue(cell):
    return len(cellToBird[cell])

def getCellTime(cell):
    return int(math.floor(cell/3)) + 1

birdsRemain = 4

while(birdsRemain > 0):

    bestCell = 0;

    for thisCell in cellsNotPicked:

        currentCellValue = getCellValue(thisCell);

        currentCellTime = getCellTime(thisCell)
        highestCellTime = getCellTime(bestCell)

        if(currentCellTime > highestCellTime):
            currentCellValue = currentCellValue - currentCellTime;

        if(currentCellValue < getCellValue(bestCell)):
            bestCell = thisCell
        elif (currentCellValue == getCellValue(bestCell)) and (currentCellTime < getCellTime(bestCell)):
            bestCell = thisCell

    picks.append(bestCell)
    cellsNotPicked.remove(bestCell)

    birdsToRemove = cellToBird[bestCell]

    for key in cellToBird:
        for bird in birdsToRemove:
            try:
                cellToBird[key].remove(bird)
                birdsRemain -= 1
            except:
                pass

print picks
1
дададзена
+1 Перш за ўсё, дзякуй за ваш час. Я ператварыў алгарытм ў рэальны код, але, вядома, можа быць памылка ў маім кодзе, таму што адказ ён дае мне гэта [9,10], як клетка выбраць. Я спрабую адладжваць яго ў цяперашні час і будзе размяшчаць назад, калі я даведаюся, што здарылася з ім. Сам код даволі трывіяльны, каб зразумець, і я паспрабаваў выкарыстаць адны і тое ж слова, як вы выкарыстоўвалі ў алгарытме, так што мы можам гаварыць на адной мове :)
дададзена аўтар Legend, крыніца
@Legend Дабра запрашаем, дзякуй за галаваломкі! Гэта даволі цікава. Ва ўсякім выпадку, я пабег уверх і ўніз некалькі разоў кода, я не магу ўбачыць, што такога асаблівага ў клетцы 9, што абраў бы гэта. Што гэта абраць першы? Дарэчы, гэта, здаецца, вы паніжаючы birdsRemain на 1 для кожнага дубліката птушкі знятай. Што прымушае мяне падазраваць, што выбірае 9 першым, не выдаляе і ня птушак, а затым выбірае 10, які прыносіць amountOfBirds -2. Але, можа быць, я проста не разумею, код пітона дастаткова добра пакуль. ^^
дададзена аўтар Aberrant, крыніца