Ordinal coefficient of sequence

Question

0.00/5 (No votes)

See more:

I am working now on search using Simulated Annealing and the function that estimates states can be expressed in an array of symbols as ("-1" means a black ball on the board, "0" - gap on the board, "1" - a white ball on the board). Initially balls located like this: "-1,-1,-1,-1,0,1,1,1" and the goal state is to reach sequence of "1,1,1,0,-1,-1,-1,-1". Cost of each transformation is 0 (zero). I need to know the algorithm that gives a coefficient of how close each successive state to the goal state. It will be used in the Simulated Annealing processing to select the best state. I suppose it's like an "ordinal hash code" of sequence, in sense that I can compare the codes to select the best one.

What I have tried:

Tried string comparison algorithms, but they don't fit to this case

Posted 9-Jan-21 10:05am

NickResh777

Updated 9-Jan-21 13:57pm

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Luc Pattyn · Accepted Answer · 2021-01-09T13:57:00

Solution 1

Hi,

strings are intended for holding text; you are dealing with numbers, so use integer arrays, or lists of integers.

A special case: if your number of positions is limited to say 32, there is an alternative where you would use two integer "bit masks", i.e. with one bit per position. The one number would describe only white balls, the other only black balls.

Your example could then be, in binary notation:
original state: W1=00000111 B1=11110000
final state: W2=11100000 B2=00000111
and your improvement function could be as simple as (W2-W1)+(B1-B2) which forces white balls to the left, black balls to the right.

:)

Posted 9-Jan-21 13:57pm

Luc Pattyn

Updated 9-Jan-21 13:58pm

v2

Comments

NickResh777 9-Jan-21 20:31pm

Thanks a lot. But how about when balls have IDs and the initial state is: [B1, B2, B3, B4, 0, W1, W2, W3] and the final state is: [W1, W2, W3, 0, B1, B2, B3, B4]? What is the optimizing function then would be?

Luc Pattyn 10-Jan-21 9:08am

When all objects are different and have a predetermined destination, the situation is completely different. Whatever their number I would keep a current position Pi and a destination position Di for each of them, and then minimize the function SUM((Pi-Di)*(Pi-Di)).

Remark: in general you can choose many different improvement or cost functions, and many of them will work well assuming they indeed yield an extreme value (minimum or maximum) on the ideal solution AND hopefully tend to monotonically evolve towards that extreme as your system nears the state you're after. A sum of squares is known to be pretty good in most cases.

:)