Jump to content

Graph Theory Proof of Concept - Artifical Intelligence


twitchyliquid64
 Share

Recommended Posts

Hi all,

This is a short program I wrote to demonstrate the power of graph theory and its potential in Autoit.

Posted Image

Ultimately, graph theory is about dynamically creating records about specific ‘things’ in your program, and mapping how they relate, to allow your program to make inferences and do something smart.

Credit must be given to toady for the idea, and for minor internal management (I used his string regexp expression, and some array popping) Here is his one: http://www.autoitscript.com/forum/topic/...rtificial-intelligence-bot-pat

I would encourage you to first download the script and try it out. Place nodes around the place, then use the link tool to link nodes of your choosing together. Then, press setup, choose the start and end nodes, then press go. Then the program will find the shortest path from start to end, traversing the links you created.

If you want to find out what graph theory is, I encourage you to look at the Wikipedia entry and Google ‘shortest path problem’.

LEMME KNOW OF YOUR OPINIONS/COMMENTS!!!

Downloads:

The Program: Node Graph Simulator.au3

My Node-Graph Theory UDF (you will need it to run): node_graph UDF.au3

Regards,

Hypoz.

Edited by hyperzap

ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

Link to comment
Share on other sites

Wow, very cool! I'd like to see a network tool built around this. Thanks for sharing!

Thanks. I'm building a wikipedia relation algorithm ATM but after that I'll rewrite my p2p udf to use this for message routing.

ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

Link to comment
Share on other sites

I'm not sure how you would use this for that: that sounds more like dynamic thresholding (using standard deviation) and a genetic algorithm.

ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

Link to comment
Share on other sites

How about going through and adding the chinese postman / eulerian graphs solutions, and the minimum spanning trees algorithms... I was thinking about doing something just like it a while ago, but wanted to build in all kinds of fancy user interfaces which I suck at. The only thing I'd add though is being able to weight the arcs.

@tobject

You are looking at linear programming there, for which you need simplex. Here is what I use to do all the working for me. Since it has to print the workings, there is a lot in there that can be stripped (there is a fair bit of code for using the letters, and an extra row and column in the tableau.

#AutoIt3Wrapper_Change2CUI=y
#AutoIt3Wrapper_Res_LegalCopyright=Matt Diesel (Mat) 2010 - 2011

Local $iNumVars = 2

Local $sObjectiveVarName = "P"
Local $aVarNames[$iNumVars] = ["x", "y"]
Local $aSlackNames[$iNumVars] = ["s", "t"]

Local $aMaxEquation[$iNumVars] = [-6, -8]
Local $aSubjectTo[$iNumVars][$iNumVars + 1] = [[4, 3, 1500],[1, 2, 500]]

_Simplex_Working($iNumVars, $sObjectiveVarName, $aVarNames, $aSlackNames, $aMaxEquation, $aSubjectTo)

Func _Simplex_Working($iNumVars, $sObjectiveVarName, $aVarNames, $aSlackNames, $aMaxEquation, $aSubjectTo)
    ; 1.1 :: Print it
    Local $sProblem = "Maximise " & $sObjectiveVarName & " = "
    For $i = 0 To $iNumVars - 1
        $sProblem &= $aMaxEquation[$i] * -1 & $aVarNames[$i] & " + "
    Next
    $sProblem = StringTrimRight($sProblem, 3)

    $sProblem &= @LF & "Subject to: " & @LF
    For $n = 0 To $iNumVars - 1
        $sProblem &= "    "

        For $i = 0 To $iNumVars - 1
            $sProblem &= $aSubjectTo[$n][$i] & $aVarNames[$i] & " + "
        Next

        $sProblem &= $aSlackNames[$n] & " = " & $aSubjectTo[$n][$iNumVars] & @LF
    Next
    ConsoleWrite($sProblem & @LF)

    ; 2 :: Initial Tableau
    $aTableau = _Simplex_CreateTableau($iNumVars)

    ; 2.1 :: Headers
    $aTableau[0][0] = "Basic var"
    For $i = 1 To $iNumVars
        $aTableau[$i][0] = $aSlackNames[$i - 1]
    Next
    $aTableau[$iNumVars + 1][0] = $sObjectiveVarName
    For $i = 1 To $iNumVars
        $aTableau[0][$i] = $aVarNames[$i - 1]
    Next
    For $i = 1 To $iNumVars
        $aTableau[0][$iNumVars + $i] = $aSlackNames[$i - 1]
    Next
    $aTableau[0][$iNumVars * 2 + 1] = "Value"

    ; 2.2 :: Values
    For $n = 0 To $iNumVars - 1
        For $i = 0 To $iNumVars - 1
            $aTableau[$n + 1][$i + 1] = $aSubjectTo[$n][$i]
        Next
        For $i = $iNumVars To $iNumVars * 2
            $aTableau[$n + 1][$i + 1] = 0
        Next
        $aTableau[$n + 1][$iNumVars + 1 + $n] = 1
        $aTableau[$n + 1][$iNumVars * 2 + 1] = $aSubjectTo[$n][$iNumVars]
    Next

    For $i = 1 To $iNumVars
        $aTableau[$iNumVars + 1][$i] = $aMaxEquation[$i - 1]
    Next
    For $i = $iNumVars To $iNumVars * 2
        $aTableau[$iNumVars + 1][$i + 1] = 0
    Next

    ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)


    Do
        _Simplex_Next($aTableau)
        ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)
        ; 7.1 :: Check optimal
    Until _Simplex_Optimal($aTableau)

    ; 7.2 :: Print solution
    Local $sSolution = "Solution: " & @LF
    For $n = 0 To $iNumVars
        $sSolution &= $aTableau[$n + 1][0] & " = " & $aTableau[$n + 1][UBound($aTableau, 2) - 2] & @LF
    Next
    $sSolution &= "Everything else = 0" & @LF
    ConsoleWrite($sSolution)
EndFunc


Func _Simplex_Next(ByRef $aTableau)
    Local $iPivotRow = -1
    Local $iPivotCol = -1

    ; 3 :: Get pivot col
    Local $r = UBound($aTableau) - 1
    For $c = 1 To UBound($aTableau, 2) - 1
        If $iPivotCol < 0 Or $aTableau[$r][$c] < $aTableau[$r][$iPivotCol] Then $iPivotCol = $c
    Next

    ; 4 :: Get pivot row
    $c = UBound($aTableau, 2) - 2
    Local $iTheta
    For $r = 1 To UBound($aTableau) - 2
        $iTheta = $aTableau[$r][$c] / $aTableau[$r][$iPivotCol] ; Theta = Value / Pivot value

        If $iTheta < 0 Then
            $aTableau[$r][$c + 1] = "--"
        Else
            $aTableau[$r][$c + 1] = "Theta = " & $iTheta

            If $iPivotRow < 0 Or $iTheta < $aTableau[$iPivotRow][$c] / $aTableau[$iPivotRow][$iPivotCol] Then $iPivotRow = $r
        EndIf
    Next
    $aTableau[UBound($aTableau) - 1][UBound($aTableau, 2) - 1] = ""

    $aTableau[0][UBound($aTableau, 2) - 1] = "Pivot: " & $iPivotRow & "," & $iPivotCol ;;;;;

    ; leaves the basis:
    $aTableau[$iPivotRow][0] = $aTableau[0][$iPivotCol]

    ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)

    ; 5 :: Divide row by pivot:
    Local $iPivot = $aTableau[$iPivotRow][$iPivotCol]
    For $c = 1 To UBound($aTableau, 2) - 2
        $aTableau[$iPivotRow][$c] /= $iPivot
    Next

    ; 6 :: Zero other rows
    Local $iTimes
    For $r = 1 To UBound($aTableau) - 1
        If $r = $iPivotRow Then ContinueLoop

        $iTimes = $aTableau[$r][$iPivotCol] / $aTableau[$iPivotRow][$iPivotCol]
        For $c = 1 To UBound($aTableau, 2) - 2
            $aTableau[$r][$c] -= $iTimes * $aTableau[$iPivotRow][$c]
        Next
        $aTableau[$r][UBound($aTableau, 2) - 1] = StringFormat("[%d] = [%d] - (%d * [%d])", $r, $r, $iTimes, $iPivotRow)
    Next
    $aTableau[$iPivotRow][UBound($aTableau, 2) - 1] = StringFormat("[%d] = [%d] / %d", $iPivotRow, $iPivotRow, $iPivot)
EndFunc   ;==>_Simplex_Next

Func _Simplex_Optimal($aTableau)
    Local $r = UBound($aTableau) - 1

    For $c = 1 To UBound($aTableau) - 1
        If $aTableau[$r][$c] < 0 Then Return False
    Next

    Return True
EndFunc   ;==>_Simplex_Optimal

Func _Simplex_TableauToString($aTableau)
    Local $sRet = ""

    For $r = 0 To UBound($aTableau) - 1
        For $c = 0 To UBound($aTableau, 2) - 2
            $sRet &= StringFormat("| %-10.10s", $aTableau[$r][$c])
        Next
        $sRet &= "| " & $aTableau[$r][UBound($aTableau, 2) - 1] & @LF
    Next

    Return $sRet
EndFunc   ;==>_Simplex_TableauToString

Func _Simplex_CreateTableau($iNumVars)
;~ Rows: $iNumVars + 2
;~ Cols: $iNumVars * 2 + 2
    Local $aTableau[$iNumVars + 2][$iNumVars * 2 + 3]

    Return $aTableau
EndFunc   ;==>_Simplex_CreateTableau

Mat

Link to comment
Share on other sites

This is based on this right: ?

Might want to give credit.

I will/have updated the main post.

True, I did draw inspiration and stringregexp from toady, but a breadth first search algorithm with unlimited edges is a world of difference to a star with heuristics and limited edges.

In any case I do owe credit to toady.

ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

Link to comment
Share on other sites

I will/have updated the main post.

True, I did draw inspiration and stringregexp from toady, but a breadth first search algorithm with unlimited edges is a world of difference to a star with heuristics and limited edges.

In any case I do owe credit to toady.

I hear you and I agree. There are lots of changes in your script, but the likeness between your code and toady was quite apparent. I didn't actually compare number of lines or anything like that, so I had no idea how much there is actually alike. On behalf of toady, I thank you. 8) Maybe a link to his A* topic would both serve toady and anyone else looking for path finding algorithms.
Link to comment
Share on other sites

I hear you and I agree. There are lots of changes in your script, but the likeness between your code and toady was quite apparent. I didn't actually compare number of lines or anything like that, so I had no idea how much there is actually alike. On behalf of toady, I thank you. 8) Maybe a link to his A* topic would both serve toady and anyone else looking for path finding algorithms.

Yea a link would help others lookin for path finding mechanisms.

Toadys A* is alot better for geometric purposes, cause it allows heuristics to influence the order of searching nodes, increasing speed.

However, you can only have max 8 neighbours and it only works when there are geometry relations, so its not good for dynamic things like networking.

Thats why I made this script; To develop my P2P UDF into an onion router.

(FULL STOP =])

ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...