JavaScript zapobiec nieskończonej pętli - z możliwością szybkiego rozpoznawania?

Question

przede oto skomentował pseudo-kod:

// TODO: 
// Person A (80kg) nutrition intake requirements are: 
// nutrient  || Unit(g) 
// Vitamin A : 30, 
// Vitamin B1 : 2, 
// Vitamin C : 300, 
// Vitamin D : 3000, 
// Protein  : 100, 
// Calcium  : 30 

var nutrient_requirements = { 
    vita: {min: 30 ,max: 38}, 
    vitb1: {min:2, max:4}, 
    vitc: {min:300, max: 800}, 
    vitd: {min: 300, max:3000}, 
    protein: {min:100, max:200}, 
    calcium: {min:30, max:50} 
} 

// The calculated estimate amount of food 
// the person eats on a daily base is around 900(g) 
// The amount will be distributed among the terms 
// with a predefined pattern 

var food_amount = { 
    fruits:[200,200], 
    meat: [500] 
} 

// START (usefull anchor for this pseudocode) 

var calculated_nutrition = { 
    vita: 0, 
    vitb1: 0, 
    vitc: 0, 
    vitd: 0, 
    protein: 0, 
    calcium: 0 
} 

// The daily nutrition intake of this person 
// needs to be achieved by the following terms: 
// apple, banana, chicken breast 
// Term nutrient values per gramm 
var terms = { 
    fruits:[ 
    apple:{ 
     vita: 0.02, 
     vitc: 0.30, 
     vitd: 0.01, 
     protein: 0.08, 
     calcium: 0 
    }, 
    banana:{ 
     vita: 0.1, 
     vitc: 0.09, 
     vitd: 0.00, 
     protein: 0.1, 
     calcium: 0.2 
    } 
    ], 
    meat:[ 
    chicken_breast:{ 
     vita: 0.07, 
     vitc: 0.08, 
     vitd: 0.03, 
     protein: 0.4, 
     calcium: 0.2 
    } 
    ] 
} 

// Now we want to see if the normal amount and distribution 
// of the food covers the required amount 
// To do that we need to multiply the matching food amount 
// with the matching food/term and sum up all values 

for(let prop in terms){ 
    for(let i = 0; i < terms[prop].length; i++){ 
    for(let propb in terms[prop][i]){ 
     calculated_nutrition[propb] = terms[prop][i][propb] * food_amount[prop][i]; 
    } 
    } 
} 

// After that is done, we can compare calculated_nutrition to 
// nutrient_requirements to see whether something is too much 
// or too little 

for(let propa in nutrient_requirements){ 
    if(nutrient_requirements[propa].min > calculated_nutrition[propa]){ 
    // this nutrient level is too little 
    // now we need to increase some food/term 
    // in order to achieve the required minimum 
    // of this nutrient 
    alter_amount(propa, "up"); 
    return; 
    }else if(nutrient_requirements[propa].max < calculated_nutrition[propa]){ 
    // this nutrient level is too high 
    // now we need to decrease some food/term 
    // in order to achieve the required minimum 
    alter_amount(propa, "down"); 
    return; 
    }else{ 
    // this nutrient level is ok 
    return; 
    } 
} 

function alter_amount(prop, direction){ 
    // here we look in terms which food 
    // has the highest amount of prop 

    switch(direction){ 
    case "down": 
     // here we decrease the amount of 
     // the matching term in the amount object 
      // and re-run this whole calculation from 
     // point START 
     break; 
    case "up": 
     // here we increase the amount of 
     // the matching term in the amount object 
      // and re-run this whole calculation from 
     // point START 
    break; 
    } 
} 

Pozwól mi krótko wyjaśnić ten przykład.

Obliczony oczekiwany wynik jest taki, że osoba musi zjeść X ilość jabłek, kwotę Y bananów i ilość piersi kurczaka dziennie, aby osiągnąć dzienny cel żywieniowy.

W moim pseudo-kodzie zapisałem podstawową funkcjonalność mojego programu, a obecny problem, z jakim się borykam, polega na tym, że JEŚLI konkretna żywność jest idealnie dopasowana do zwiększenia ilości w jednej pętli, a następnie dzieje się Idealnie pasuje do zmniejszenia ilości w innej pętli - kończę w nieskończonej pętli.

Na podstawie mojego minimalistycznego przykładu mogłem zakodować, że jeśli ilość jabłka wzrośnie, nie powinno się zmniejszać w następnej pętli - ale w moim programie na świecie pracuję z większym składnikiem składników z wieloma dodatkami . Tak więc złożoność, aby pokryć to, podnosi się niezwykle.

Szukam sposobu na rozpoznanie wzoru, który nie daje rezultatu i nakazuje programowi wybrać drugą najlepszą potrawę do zwiększenia lub zmniejszenia, aby nie zakończyć się nieskończoną pętlą.

że coś takiego dostaje unikać:

apple ++ 
apple ++ 
banana ++ 
apple ++ 
banana ++ 
meat -- 

apple -- 
apple -- 
banana -- 
apple -- 
banana -- 
meat ++ 

apple ++ 
apple ++ 
banana ++ 
apple ++ 
banana ++ 
meat -- 

apple -- 
apple -- 
banana -- 
apple -- 
banana -- 
meat ++ 
... 

EDIT

Odpowiedź podane poniżej promowanie trochę hashowania i przechowywania systemu prowadzi do tego samego wyniku którego doświadczenie z moją czarną listę niestandardowej metody.

Moja czarna lista metoda działa w następujący sposób:

Jabłko kwota została zmieniona (obniżanie/przyrost) -> Zapisz że na czarnej tablicy.

blacklist = [{product: "apple", altered: "down/up"},...] 

Teraz na każdej pętli przed wyborem żywności do zwiększenia lub zmniejszenia czarna lista jest skanowana. Jeśli idealne dopasowanie znajduje się w szyku, wybierane jest drugie najlepsze dopasowanie i tak dalej.

Istnieje kilka dodatkowych ograniczeń, takich jak: f.e. Jabłka nie mogą być większe niż x% całkowitej kwoty. Lub jabłka nie mogą być mniejsze niż x% całkowitej kwoty.

W połączeniu z ograniczeniami + na czarnej liście produktów mój program kończy się w stanie, w którym nie ma ona więcej różnych pokarmów zwiększać lub zmniejszać i po prostu zmienia nic, a kończy w nieskończonej pętli bez progresji

I don Nawet nie wiem, czy istnieje sposób na rozwiązanie tego problemu programowo - czy też muszę po prostu powiedzieć "hej, problem ten nie da się rozwiązać".

Wszystko, co mogę wymyślić, to sposób na zaimplementowanie funkcjonalności, którą program rozpoznaje jako "zablokowany" -> pamięta wzorzec, który prowadzi do stanu zatrzymania i próbuje ponownie z innym podejściem. Ale to może być przesada w myślach.

Answer 1

Rozwiązaniem jest zapamiętywanie zestawu wszystkich stanów, które odwiedziłeś wcześniej i unikanie dwukrotnego wprowadzania stanu (oznacz go jako "tabu").

Jeżeli zmiana stanu jest mała (tzn jeśli tylko zmutować kilka wartości), wówczas przydatna sztuczka jest użycie "zobrist hashing" tak, że kod skrótu dla następnego stanu mogą być obliczane w O(n) gdzie n jest liczba zmian a nie liczba zmiennych

Answer 2

Na podstawie Twojego opisu, myślę, że masz do czynienia z klasycznym (Unbounded) Knapsack Problem, którego celem jest znalezienie najlepszej kombinacji elementów (rodzajów żywności) do osiągnięcia danego pomiaru (suma Wasz pseudokodek nie może rozwiązać tego problemu prawidłowo. wymienione w pytaniu, na przykład:

• Jaka jest waga każdego odżywiania?
• Czy jeden sposób żywienia może trochę przewyższyć, aby osiągnąć lepsze wyniki?
• Jak zdecydować, które combo jest lepsze? (Jak zmniejszyć combo do wyniku?)
• Kiedy jest kilka kombinacji uznawanych za równie dobre, jak zdecydujesz, który z nich pójdzie?

Otrzymasz mniej niż idealne wyniki, jeśli na te pytania nie udzielono odpowiedzi. Kiedy wszystko pójdzie źle, utkniesz w algorytmie.

Napisałem fragment, aby zademonstrować rozwiązanie problemu z bruteforce, używając moich osobistych przemyśleń jako odpowiedzi na powyższe pytania, z 2 odżywkami i 2 rodzajami żywności.

Podczas gdy przestrzeń problemowa bardzo szybko się komplikuje przy dodawaniu składników odżywczych/rodzaju żywności, zawsze można wprowadzić różne poprawki, aby upewnić się, że działa ona w rozsądnym czasie w nowoczesnej przeglądarce.

Zobacz JSFiddle. (Możesz wyłączyć opcję zawijania linii.)