In-Development TradeDangerous: power-user trade optimizer

Avi0013

Avi0013
MarkAusten said:
Okay, first off let me prefix this post with a warning: I'm not a python programmer. However, I have been programming in one form or another for the last 48 years most of which have been as a professional programmer so I have an idea of what programming is all about. Sort of.…I'm just going to do a few metrics to find out if the depth of recursion is linear or exponential or whatever, mainly because I want to know :)
Click to expand...
Shweeet. I'm neither a Python programmer nor a programmer of any kind. I don't even play one on the radio. I just pretend to be one for the cool free stuff. That being said, I have been puttering around math and statistics for the last 15 or so years, so I know just enough to get myself into deep trouble.

The knapsack problem, of which this is, is factorial/exponential since it is a combinatorial optimization. That means the optimization is NP-hard so a true solution is not possible in polynomial time (that we know of). The recursion that Oliver programmed is probably the formally correct approach, which means it's going to explode factorially (which makes exponential growth look slow for a fixed base as n! climbs faster than e^n). There are approximations that run faster, see <https://en.wikipedia.org/wiki/Knapsack_problem#Solving> which I will leave to the real programmers among us.

[EDIT]
It's not even that simple as a standard knapsack, since we aren't starting with the full suite of items, their weights, and their costs, but the set of allowable inputs varies on the path we are taking as well. Oy Vey.
 
Last edited:

MarkAusten

MarkAusten
Avi0013 said:
Shweeet. I'm neither a Python programmer nor a programmer of any kind. I don't even play one on the radio. I just pretend to be one for the cool free stuff. That being said, I have been puttering around math and statistics for the last 15 or so years, so I know just enough to get myself into deep trouble.

The knapsack problem, of which this is, is factorial/exponential since it is a combinatorial optimization. That means the optimization is NP-hard so a true solution is not possible in polynomial time (that we know of). The recursion that Oliver programmed is probably the formally correct approach, which means it's going to explode factorially (which makes exponential growth look slow for a fixed base as n! climbs faster than e^n). There are approximations that run faster, see <https://en.wikipedia.org/wiki/Knapsack_problem#Solving> which I will leave to the real programmers among us.

[EDIT]
It's not even that simple as a standard knapsack, since we aren't starting with the full suite of items, their weights, and their costs, but the set of allowable inputs varies on the path we are taking as well. Oy Vey.
Click to expand...

Avi0013 said:
For the mathematically inclined, it seems that TD's problem is sometimes called the "shortest path knapsack problem". See <http://www.iraj.in/journal/journal_file/journal_pdf/3-334-148886853831-34.pdf>. For our purposes, we may be better off limiting the depth of the recursion for the general question (without other possibly ameliorating constraints like loop or fixed finish point).
Click to expand...

This is also known as the bounded knapsack problem, which is a nuisance since it eliminates at least one useful approximate solution.

So, metrics...

The time taken for the 20-25 trade items per route is as follows;

20 : 4.75 (4.75)
21 : 9.50 (9.50)
22 : 18.80 (19.00)
23 : 38.50 (38.00)
24 : 69.00 (76.00)
25 :144.00 (152.00)

The numbers in brackets show the expected time if the curve is exponential of 2^n starting at 4.75 seconds

So, it is approximately exponential and definitely not linear.

The items form the getTrades method only return the items between the two stations that show a profit, no matter how small, so we either cut down the number origins being checked, the number of items in the trades list or reduce the recursion somehow or a combination of all of these.

One way of ensuring that the number of origins is small is to ensure that the gains-per-ton parameter is set to a reasonable figure. Using the following command gives the number of origins shown in the spoiler below that:

trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --loop --summary -vv --progress

* Hop 2: .....1,531 origins .. 15,120-2,359,221cr gain, 21-3,276cr/ton

--gpt=10

* Hop 2: .....1,531 origins .. 15,120-2,359,221cr gain, 21-3,276cr/ton

--gpt=100

* Hop 2: .....1,377 origins .. 73,440-2,359,221cr gain, 102-3,276cr/ton

--gpt=1000

* Hop 2: .......894 origins .. 292,677-2,359,221cr gain, 1,085-4,177cr/ton

--gpt=2000

* Hop 2: .......793 origins .. 462,462-2,359,221cr gain, 2,002-4,177cr/ton

--gpt=3000

* Hop 2: .......267 origins .. 696,465-2,359,221cr gain, 3,015-4,177cr/ton

--gpt=4000

* Hop 2: ........83 origins .. 924,924-964,887cr gain, 4,004-4,177cr/ton

Note that we have a discrepancy here. For a GPT in the range 0 to 1000 the calculated maximum cr / ton is 3,276. For the rest of the time this is 4,177. So the initial algorithm is in error somewhere since I would expect that figure to be 4,177 no matter what value is assigned to the GPT (or not).

However, this does not appear to affect the number of items in the trade list. I would have expected the trade list to also be bounded by the GPT but it appears that the full trade list is returned each time.

Some items could be eliminated from this list if, for example, the total profit (unit profit * number of tons available) of the item with the lowest profit is less than one of the items with the highest profit. Pruning the trades list in this way may reduce the number of items to a better number. On my computer that would be around 15 items or 150mS per route.

It may be a simple as only returning the 15 most profitable items if there are more than that number in the list.

There may be other ways to reduce this but I'll hand that over to the mathematicians out there.
 
Last edited:

Avi0013

Avi0013
I believe the concern is similar to that of pruning scores. It may be that a less profitable node at level 2 allows access to a more profitable node at level 3 or 4.

Would it help if we were to pull all the data from all "possible" stations (possibly restricted) into some master table first, augment the weights to reflect distance, and then treat that as a single knapsack problem? We may be able to get out of the recursion if we limit the universe of possible stations and populate them first. Maybe. Just brainstorming.
 

Avi0013

Avi0013
Recursion, do we even need it here?

OK. I don't know if this is technically correct, but it does address @MarkAusten's problem.

What bothered me a bit is the combination of the for loop and the recursion in fastFit's _fitCombos. If we're recursing calling iNo+1 and relying on the break when maxQTy = cap, why loop? And if we're going to loop, why recurse?

So I made the following changes locally. First, the minor one:
Code: 
               supply = item.supply
                # if supply > 0:
                    # maxQty = min(maxQty, supply)
                    
                if supply <= 0: #If there is no supply, then move on!
                    continue
                else:
                    maxQty = min(maxQty, supply)

If supply is <= 0 just move to the next item like it does when maxQty <= 0

More importantly, I commented out the recursion and, instead, decremented cap and cr at the end of the loop, and broke if either were <= 0. The idea being that we don't need to recurse. We fill the first item. If we haven't exhausted, then move to the next item with the lower caps, exactly as the recursion would have done, but via a loop. If we were moving nodes or stations, we couldn;'t have done this, but this is all for one station. The recursion only passed iNo+1 and the lower caps; do that in the loop!
Code: 
    def fastFit(self, items, credits, capacity, maxUnits):
        """
            Best load calculator using a recursive knapsack-like
            algorithm to find multiple loads and return the best.
        """

        def _fitCombos(offset, cr, cap):
            """
                Starting from offset, consider a scenario where we
                would purchase the maximum number of each item
                given the cr+cap limitations. Then, assuming that
                load, solve for the remaining cr+cap from the next
                value of offset.

                The "best fit" is not always the most profitable,
                so we yield all the results and leave the caller
                to determine which is actually most profitable.
            """

            bestGainCr = -1
            bestItem = None
            bestQty = 0
            bestCostCr = 0
            bestSub = None

            qtyCeil = min(maxUnits, cap)

            for iNo in range(offset, len(items)):
                item = items[iNo]
                itemCostCr = item.costCr
                maxQty = min(qtyCeil, cr // itemCostCr)

                if maxQty <= 0:
                    continue

                supply = item.supply
                # if supply > 0:
                    # maxQty = min(maxQty, supply)
                    
                if supply <= 0: #If there is no supply, then move on!
                    continue
                else:
                    maxQty = min(maxQty, supply)

                itemGainCr = item.gainCr
                if maxQty == cap:
                    # full load
                    gain = itemGainCr * maxQty
                    if gain > bestGainCr:
                        cost = itemCostCr * maxQty
                        # list is sorted by gain DESC, cost ASC
                        bestGainCr = gain
                        bestItem = item
                        bestQty = maxQty
                        bestCostCr = cost
                        bestSub = None
                    break

                loadCostCr = maxQty * itemCostCr
                loadGainCr = maxQty * itemGainCr
                if loadGainCr > bestGainCr:
                    bestGainCr = loadGainCr
                    bestCostCr = loadCostCr
                    bestItem = item
                    bestQty = maxQty
                    bestSub = None
                    
                cr -= loadCostCr
                cap -= maxQty
                if cr <= 0 or cap <= 0:
                    break

                # crLeft, capLeft = cr - loadCostCr, cap - maxQty
                # if crLeft > 0 and capLeft > 0:
                    # # Solve for the remaining credits and capacity with what
                    # # is left in items after the item we just checked.
                    # subLoad = _fitCombos(iNo+1, crLeft, capLeft)
                    # if subLoad is emptyLoad:
                        # continue
                    # ttlGain = loadGainCr + subLoad.gainCr
                    # if ttlGain < bestGainCr:
                        # continue
                    # ttlCost = loadCostCr + subLoad.costCr
                    # if ttlGain == bestGainCr and ttlCost >= bestCostCr:
                        # continue
                    # bestGainCr = ttlGain
                    # bestItem = item
                    # bestQty = maxQty
                    # bestCostCr = ttlCost
                    # bestSub = subLoad

            if not bestItem:
                return emptyLoad

            bestLoad = ((bestItem, bestQty),)
            if bestSub:
                bestLoad = bestLoad + bestSub.items
                bestQty += bestSub.units
            return TradeLoad(bestLoad, bestGainCr, bestGainCr, bestQty)

        return _fitCombos(0, credits, capacity)

Running Mark's problem is still slow (around a minute or so) but it solves, unlike the current, which I've had running in another window to close to an hour and not ONE equal sign yet!
F:\Elite\TD>trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --loop --summary -vv --progress
* Hop 1: .........1 origins
* Hop 2: .....1,531 origins .. 15,120-2,991,600cr gain, 21-4,155cr/ton
Orang/Bessel Gateway -> Orang/Bessel Gateway (score: 1925836.612706)

Load from Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
720 x Slavery/Imperial Slaves 14,325cr vs 18,266cr, 15 hrs vs 34 hrs
Expect to gain 2,837,520cr (3,941cr/ton)

Load from Erivia/Norton Survey (300Kls, BMk:N, Pad:L, Plt:Y, Shp:N, Out:Y, Ref:Y):
720 x Medicines/Basic Medicines 358cr vs 1,786cr, 17 days vs 15 hrs
Expect to gain 1,028,160cr (1,428cr/ton)
----------------------------------------------------------------------------
Finish at Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 3,865,680cr (2,684cr/ton) => est 11,003,865,680cr total

As an aside, Mark's original call with the --max-days 2 runs in about 10 seconds, and returns a less-lucrative result, which is reassuring, actually:
F:\Elite\TD>python trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --max-days-old=2 --loop --summary -vv --progress
* Hop 1: .........1 origins
* Hop 2: .......389 origins .. 15,120-2,979,360cr gain, 21-4,138cr/ton
Orang/Bessel Gateway -> Orang/Bessel Gateway (score: 1762541.819623)

Load from Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
720 x Slavery/Imperial Slaves 14,325cr vs 18,338cr, 15 hrs vs 33 hrs
Expect to gain 2,889,360cr (4,013cr/ton)

Load from CD-60 7742/Kopal Dock (657ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
720 x Consumer Items/Consumer Technology 6,653cr vs 7,524cr, 33 hrs vs 15 hrs
Expect to gain 627,120cr (871cr/ton)
----------------------------------------------------------------------------
Finish at Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 3,516,480cr (2,442cr/ton) => est 11,003,516,480cr total

Also, my two test cases tollan/gord --> LHS 204/Patt (which overflows with the correction suggested in PR #8) and MAWU/Dirac --> LHS 2094 both return the same results with and without the recursion, although the latter is faster.

Can brave people play with it and see if they can find any different results withj and without, or at least suggest some calls that used to freeze which I can test on the loop-only version? Thanks!
 

Avi0013

Avi0013
Tromador said:
I've reproduced this on a different set of parameters.

Code: 
[elite@mort tradedangerous.server]$ cat .tdrc_run
-v
--pla=YN?
--credits=50000000
--capacity=150
--ly-per=29.09
--empty-ly=33.31
--insurance=15000000
--progress
--pad-size=L

Code: 
[elite@mort tradedangerous.server]$ ./trade.py run --from fujin --to fujin --hops 4 --age 2
* Hop   1: .........1 origins
* Hop   2: .......292 origins
* Hop   3: .....1,437 origins
[==================       ] ^CTraceback (most recent call last):
  File "./trade.py", line 104, in <module>
    main(sys.argv)
  File "./trade.py", line 77, in main
    results = cmdenv.run(tdb)
  File "/home/elite/tradedangerous.server/commands/commandenv.py", line 81, in run
    return self._cmd.run(results, self, tdb)
  File "/home/elite/tradedangerous.server/commands/run_cmd.py", line 1220, in run
    newRoutes = calc.getBestHops(routes, restrictTo=restrictTo)
  File "/home/elite/tradedangerous.server/tradecalc.py", line 909, in getBestHops
    trade = fitFunction(items, startCr, capacity, maxUnits)
  File "/home/elite/tradedangerous.server/tradecalc.py", line 700, in fastFit
    return _fitCombos(0, credits, capacity)
  File "/home/elite/tradedangerous.server/tradecalc.py", line 676, in _fitCombos
    subLoad = _fitCombos(iNo+1, crLeft, capLeft)
  File "/home/elite/tradedangerous.server/tradecalc.py", line 676, in _fitCombos
    subLoad = _fitCombos(iNo+1, crLeft, capLeft)
  File "/home/elite/tradedangerous.server/tradecalc.py", line 676, in _fitCombos
    subLoad = _fitCombos(iNo+1, crLeft, capLeft)
  [Previous line repeated 7 more times]
  File "/home/elite/tradedangerous.server/tradecalc.py", line 637, in _fitCombos
    for iNo in range(offset, len(items)):
KeyboardInterrupt

And can you guess what happened when I added in a supply term?

Code: 
[elite@mort tradedangerous.server]$ ./trade.py run --from fujin --to fujin --hops 4 --age 2 --supply=20
* Hop   1: .........1 origins
* Hop   2: .......289 origins
* Hop   3: .....1,433 origins
NOTE: Pruned 2361 origins too far from any end stations
* Hop   4: .......375 origins
Fujin/Futen Spaceport -> Fujin/Futen Spaceport (score: 1694090.676000)
  Load from Fujin/Futen Spaceport: 150 x Foods/Coffee (@1041cr),
  Dock at Capo/McCaffrey City
  Load from Capo/McCaffrey City: 150 x Medicines/Basic Medicines (@288cr),
  Dock at Fujin/Futen Spaceport
  Load from Fujin/Futen Spaceport: 150 x Foods/Coffee (@1041cr),
  Dock at Capo/McCaffrey City
  Load from Capo/McCaffrey City: 150 x Medicines/Basic Medicines (@288cr),
  Dock at Fujin/Futen Spaceport
  Finish Fujin/Futen Spaceport + 1,693,500cr (2,822cr/ton)=> 51,693,500cr

To further test, I changed to supply=1 and produced the error case. The idea of putting a default supply=1 was mentioned somewhere (might have been when I was chatting with Eyeonus) but clearly that isn't a fix. Also we can't reasonably put a higher default, as that would impact users with very small ships[1].
On the other hand, if I tell TD I only have 1 ton of space (without a supply term), it gives me a perfectly good route, but for just the one ton.

[1] I find it hard to believe people are using trade tools for their 1 ton of cargo room, but anyway.
Click to expand...

Granted, the database has been updated, but running Tromador's call with the non-recursion version finished relatively quickly and the "unsupplied" version does return more credits than the supplied version.

F:\Elite\TD>trade.py run --from fujin --to fujin --hops 4 --age 2 -vvv --summary --pla=YN? --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress --pad-size=L
* Hop 1: .........1 origins
* Hop 2: .......290 origins .. 420-180,600cr gain, 6-1,204cr/ton
* Hop 3: .....1,469 origins .. 6,900-835,350cr gain, 23-2,784cr/ton
NOTE: Pruned 2408 origins too far from any end stations
* Hop 4: .......379 origins .. 536,700-1,227,000cr gain, 1,192-2,771cr/ton
Fujin/Futen Spaceport -> Fujin/Futen Spaceport (score: 1231169.282605)
Start CR: 35,000,000
Hops : 4
Jumps : 8
Gain CR : 1,228,160
Gain/Hop: 307,040
Final CR: 36,228,160


Load from Fujin/Futen Spaceport (561ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Chemicals/Water 42cr vs 642cr, 1 hr vs 34 hrs, total: 6,300cr
Expect to gain 90,000cr (600cr/ton)

Load from Capo/McCaffrey City (1.29Kls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Slavery/Imperial Slaves 14,260cr vs 17,211cr, 34 hrs, total: 2,139,000cr
Expect to gain 442,650cr (2,951cr/ton)

Load from Zeus/The Midas (8ls, BMk:N, Pad:L, Plt:N, Shp:N, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 273cr vs 4,902cr, 34 hrs vs 26 hrs, total: 40,950cr
Expect to gain 694,350cr (4,629cr/ton)

Load from Thethys/Dantius Citadel of House Thiemann (498ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
4 x Waste/Biowaste 57cr vs 347cr, 26 hrs vs 1 hr, total: 228cr
Expect to gain 1,160cr (290cr/ton)
----------------------------------------------------------------------------
Finish at Fujin/Futen Spaceport (561ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,228,160cr (2,705cr/ton) => est 51,228,160cr total


F:\Elite\TD>trade.py run --from fujin --to fujin --hops 4 --age 2 -vvv --summary --pla=YN? --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress --pad-size=L --supply=20
* Hop 1: .........1 origins
* Hop 2: .......290 origins .. 420-180,600cr gain, 6-1,204cr/ton
* Hop 3: .....1,466 origins .. 6,900-835,350cr gain, 23-2,784cr/ton
NOTE: Pruned 2406 origins too far from any end stations
* Hop 4: .......379 origins .. 536,700-1,227,000cr gain, 1,192-2,726cr/ton
Fujin/Futen Spaceport -> Fujin/Futen Spaceport (score: 1196761.721232)
Start CR: 35,000,000
Hops : 4
Jumps : 7
Gain CR : 1,200,150
Gain/Hop: 300,038
Final CR: 36,200,150


Load from Fujin/Futen Spaceport (561ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Chemicals/Mineral Oil 143cr vs 1,331cr, 1 hr vs 37 hrs, total: 21,450cr
Expect to gain 178,200cr (1,188cr/ton)

Load from Fular/Kotov Orbital (1.36Kls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 521cr vs 4,598cr, 37 hrs vs 16 hrs, total: 78,150cr
Expect to gain 611,550cr (4,077cr/ton)

Load from 9 Aurigae/Hunt Enterprise (67Kls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Metals/Silver 4,376cr vs 5,605cr, 16 hrs vs 3 hrs, total: 656,400cr
Expect to gain 184,350cr (1,229cr/ton)

Load from Tote/Whitelaw Enterprise (1.10Kls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Performance Enhancers 5,845cr vs 7,352cr, 3 hrs vs 1 hr, total: 876,750cr
Expect to gain 226,050cr (1,507cr/ton)
----------------------------------------------------------------------------
Finish at Fujin/Futen Spaceport (561ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,200,150cr (2,000cr/ton) => est 51,200,150cr total
 

eyeonus

E
Tiny, quick thing:

You don't need the else in the supply check because 'continue' skips everything and goes straight to the next iteration, so the following line will only call when supply > 0:
Code: 
                if supply <= 0: #If there is no supply, then move on!
                    continue
                maxQty = min(maxQty, supply)
As to why it loops and recurses:
It loops to find the best profit item.
On items that don't fill the hold completely, it recurses to find the most profitable item in the list not including the current item.

I think it might be a better idea to double-loop:
loop1: Go through each item and create a list containing each item, its profit, and the maxSupply, sorted by profit.
loop2: Pop the first item in the sorted list until the hold is full (or the list is empty).

I'm probably wrong on this, because my ability to calculate big-O has never been great, but I'm pretty sure the double-loop idea reduces the complexity to O(n) + O(log n), whereas the current is O(n^n).

EDIT: Um, hmm. Apparently the list is already sorted by highest profit. Okay, I need to go over this code in detail to try to figure out what it's doing.
 
Last edited:

Avi0013

Avi0013
eyeonus said:
Tiny, quick thing:

You don't need the else in the supply check because 'continue' skips everything and goes straight to the next iteration, so the following line will only call when supply > 0:
Code: 
                if supply <= 0: #If there is no supply, then move on!
                    continue
                maxQty = min(maxQty, supply)
Click to expand...
Not sure I understand you; that's my code. The original code is in lines 645-647 of current tradecalc.py:
Code: 
supply = item.supply
if supply > 0:
    maxQty = min(maxQty, supply)

eyeonus said:
As to why it loops and recurses:
It loops to find the best profit item.
On items that don't fill the hold completely, it recurses to find the most profitable item in the list not including the current item.
Click to expand...

I understand, but why doesn't the single for loop do that already? Since we don't break UNLESS maxQty == cap (line 661 is part of the `if` that starts at line 650), why recurse at line 676 if all we have to do is run lines 638–670 starting at the NEXT item with the reduced capacity and credits? We don't need recursion for that, it's the next iteration of the loop IF we adjust cap and credit?

eyeonus said:
I think it might be a better idea to double-loop:
loop1: Go through each item and create a list containing each item, its profit, and the maxSupply, sorted by profit.
loop2: Pop the first item in the sorted list until the hold is full (or the list is empty).
Click to expand...

Isn't this already the items list created by `getTrades` (702–739) in line 906 and passed to fastFit in line 909?

eyeonus said:
I'm probably wrong on this, because my ability to calculate big-O has never been great, but I'm pretty sure the double-loop idea reduces the complexity to O(n) + O(log n), whereas the current is O(n^n).
Click to expand...
[wacky]
 

eyeonus

E
No, THIS is your code:
Code: 
                if supply <= 0: #If there is no supply, then move on!
                    continue
                else:
                    maxQty = min(maxQty, supply)

Because the recursion doesn't just go through the loop with a reduced cap and credit. These are all the things done in the recursion that don't get done by simply going to the next iteration in the for loop:
Code: 
            bestGainCr = -1
            bestItem = None
            bestQty = 0
            bestCostCr = 0
            bestSub = None
And these are all the things that don't get done upon returning from the recursion if we loop instead:
Code: 
                    ttlGain = loadGainCr + subLoad.gainCr
                    if ttlGain < bestGainCr:
                        continue
                    ttlCost = loadCostCr + subLoad.costCr
                    if ttlGain == bestGainCr and ttlCost >= bestCostCr:
                        continue
                    bestGainCr = ttlGain
                    bestItem = item
                    bestQty = maxQty
                    bestCostCr = ttlCost
                    bestSub = subLoad
 

Avi0013

Avi0013
OK. Beginning to be clearer now. Thank you.

Maybe we just have to limit the recursion to a specific depth? It's clear that I'm out of my league trying to iterate the recursion. Thanks for your patience.
 

eyeonus

E
I'm currently looking at the code trying to figure out exactly what it does, because it definitely doesn't seem to be a simple matter of add most profitable thing, if maxLoad not reached add next most profitable thing, if maxLoad not....
I kind of want to make a "simpleFit" that does that just to see how it compares to the fastFit.

On that note I did notice an error:
Code: 
return TradeLoad(bestLoad, bestGainCr, bestGainCr, bestQty)
Should be:
Code: 
return TradeLoad(bestLoad, bestGainCr, bestCostCr, bestQty)

Fixed that and pushed, but I doubt that's all that needed to fix this thing.
 

Avi0013

Avi0013
I'm playing with limiting the recursion depth. Right now, on Tromodor's example, limiting it to 0 or 1 is sub-optimal, 2–4 return the same value, and 5 freezes.

As for Mark's example setting the max recursion depth to 0, 1, 2 or two finishes and give the same answer, it takes longer with a max depth of 3 and MUCH longer at 4, but still returns the same value, and did not finish on 5.

Tromodor Call:
Code: 
trade.py run --from fujin --to fujin --hops 4 --age 2 -vvv --summary --pla=YN? --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress --pad-size=L
MarkAusten Call:
Code: 
trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --loop --summary -vv --progress

Code change:
Code: 
        def _fitCombos(offset, cr, cap, recdepth):
.
.
.
.
.
                if crLeft > 0 and capLeft > 0:
                    # Solve for the remaining credits and capacity with what
                    # is left in items after the item we just checked.
                    if recdepth < 3:
                        subLoad = _fitCombos(iNo+1, crLeft, capLeft, recdepth + 1)
                        if subLoad is emptyLoad:
                            continue
                        ttlGain = loadGainCr + subLoad.gainCr
                        if ttlGain < bestGainCr:
                            continue
                        ttlCost = loadCostCr + subLoad.costCr
                        if ttlGain == bestGainCr and ttlCost >= bestCostCr:
                            continue
                        bestGainCr = ttlGain
                        bestItem = item
                        bestQty = maxQty
                        bestCostCr = ttlCost
                        bestSub = subLoad
.
.
.
return _fitCombos(0, credits, capacity, 0)
 
Last edited:

eyeonus

E
Okay, I figured out what this thing does.
It takes the first item, which has the highest profit/ton, and tries to fill the hold with it.
If the hold isn't full, it tries to fill what's left with the second item, then the third, and so on, until the hold is full, there are no more items, or there's not enough money to buy any more stuff.
^^^ This is where the recursion comes in.
It gets the total profit from this whole process, and checks to see if the total profit from this combination is better than the current "best" combination's profit.

It then goes on to the second item, repeating the entire process.
^^^ This is where the loop comes in.
 
Last edited:

Avi0013

Avi0013
So the loop is there to check that some combination of 2, 3, 4, and 5 may be better than 1, 2, and 3? No wonder it takes forever.

I'd give you extra rep for that, but it isn't letting me :(
 

eyeonus

E
Avi0013 said:
So the loop is there to check that some combination of 2, 3, 4, and 5 may be better than 1, 2, and 3? No wonder it takes forever.

I'd give you extra rep for that, but it isn't letting me :(
Click to expand...

Precisely. The thing is, it's actually the money that makes this problem so difficult.

Item 1 obviously gives the most profit/ton, but if you can only afford 2 of them, it might be better to ignore that and buy more of the cheaper item 2, because while it has a lower profit/ton, you can afford to get more of it.

Now as to why it's freezing..... I'll have to add some debug messages to figure that out.
 
You must log in or register to reply here.
Back
Top Bottom