Finding multiple paths through a grid such that every grid square is equally used


Setup

Here’s the setup: I have an $ N$ x $ N$ grid of tiles, and a list of $ M$ agents that need to move across the grid. Each agent has its own start tile $ S(a)$ , end tile $ E(a)$ , and an exact number of steps $ D(a)$ it must make. Each step consists of a one-tile move horizontally, vertically, or staying in place. For each agent, $ D(a)$ is usually much larger than the Manhattan distance between $ S(a)$ and $ E(a)$ , so the path the agent takes is not necessarily a straight line from $ S(a)$ to $ E(a)$ . Furthermore, the sum of all $ D(a)$ is expected to be much larger than $ N$ x $ N$ , so every tile will be used at least once. Agent paths are allowed to intersect with other paths and with themselves, and the number of agents on a tile at any given time doesn’t matter.

The Problem

I would like to find paths for each agent that begin at $ S(a)$ , end at $ E(a)$ , and are exactly $ D(a)$ steps long, with the goal of minimizing the maximum number of times any given tile is used. More formally, given an agent path $ P_0 \ldots P_n$ , let $ C(P, t)$ be the number of times tile $ t$ appears in $ P$ , and let $ A(t)$ be the sum of $ C(P, t)$ over all agent paths. I would like to find agent paths that minimize the maximum $ A(t)$ over all tiles $ t$ .

My intuition tells me that this problem is almost certainly NP hard, so I’m looking for some kind of approximation or heuristic.

First Attempt

My first stab at solving this was to find each path sequentially. For each agent, I create a 3-dimensional $ N$ x $ N$ x $ D(a)$ search space, then use A* search to find the min-cost path from $ [S(a), 0]$ to $ [E(a), D(a)]$ . The cost of each node in the search is the number of times that tile has been used by previous paths. Then, once the path is found, I add to the cost of each tile used, and proceed to the next agent. Of course, this leads to the problem that while the last agent path will be pretty good, the first agent path will be essentially random because the grid is yet totally unused. So, I just loop this process a few times; once the last path is computed and the tile costs updated, I loop back to the first path, subtract from the grid the costs that agent contributed, then recompute that path and add the new costs in. After 3 or 4 loops, I converge on a pretty reasonable solution.

But I’m hoping there’s a better idea out there. Any ideas or references to similar problems that I could read up on would be very welcome.

Is there really such a thing as “script kiddies”?

All my life, well, at least since the late 1990s, I’ve heard of this concept of “script kiddies”. Allegedly, it’s a term to refer to young kids or teenagers who, apparently, are somehow able to find “proof of concept” pre-coded exploit scripts of some kind, and proceed to download these to their own computers where they run them on some target website (or other server), hoping that they are unpatched/vulnerable, and, as a result, gain access to this server/computer/system.

Is, or was, this really a thing?

I was an extremely lonely “nerd” with tons of anger and frustrations. I actively looked for all kinds of sketchy stuff. But I never found anything like what I described above. I don’t believe it exists. I don’t buy that there is such a thing as a “script kiddie”.

Either that or I really was a lamer who couldn’t even find a pre-written script to run.

To me, it seems like “script kiddie” is a made-up concept. I don’t believe that it’s as simple as running a simple script to break into a system, and I don’t believe that such a script would be published in public in a way that makes “kiddies” able to find and use them.

I think the term was coined by pissed-off system administrators whose systems had been compromised, and rather than blaming themselves, the developers or “actual intruders”, they make up this idea (possibly after watching the movie “Hackers”) of there being a bunch of little annoying early teenage kids sitting there mindlessly running scripts which cause havoc.

Basically, if it had been that easy to “auto-hack” systems, this would’ve been abused far more often and automated long ago. I recognize that I’m not the smartest person in the world, and that there are extremely smart 14-year-olds, but I don’t “buy” this whole concept. I think the “script kiddie” is a nonexistent scapegoat.

It’s much easier to blame “those damn kids who don’t even know how to code” than admit that you were accepting any username/password to your world-facing database due to an embarrassing misconfiguration.

What stops you from crafting items such as wands with Shadow Evocation/Conjuration/Shades?

Since Wish/Limited Wish can indeed be used to craft items(Can you craft magic items using Wish instead of the required spell?)

What stops me from creating a wand of fireball with the help of the spell Shadow Evocation to mimic the spell instead? (or a staff since Shadow Evocation is a 5th level spell and that might not work on a wand)

There might not be RAW solutions to this, but if I ever allow this I’ll treat the wand as a Shadow Evocation (fireball) with the same limitations, but what about Wondrous items that require a certain spell to be crafted? Wish does work per RAW since it provides the prerequisites of the item.

I guess I should just not allow it, much simpler that way.

Find bipartial subgraph such that mean square deviation of edge lengths is minimum

Let there be graph $ G = (V, \, E)$ . $ G$ has neither loops nor parallel arcs.

$ V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$

For simplicity’s sake, let’s consider $ G$ is directed.

$ \forall \ e \in E \ \, e.tail \in A, \, e.head \in B, \, e.length \in (\mathbb{Z} \cap [1, 100]) \cup -\infty \ \forall \ a \in A, \, b \in B \ \ \exists! \ e \in E: e = (a, b)$

The goal is to develop an algorithm that finds a bipartite subgraph $ G’ = (V’, \, E’)$ such that:

1) $ |\,E’\;|$ is maximum;
2) Under restriction 1), $ \sum \limits_{e’ \in E’} (e’.length – (\sum \limits_{e’ \in E’} e’.length \; / \; |\, E’ \; |))^2 $ is minimum possible, where $ | \, E’ \; |$ is cardinality of $ E’$ .

For example, let graph $ G$ be defined as following: enter image description here

In this case, the correct solution is: enter image description here

The algorithm should run in polynomial time.

Can a psionic-but-no-manifesting creature use psionic powers? such as Elan with some Aegis class level?

Can a psionic-but-no-manifesting creature use psionic powers? such as Elan with some Aegis class level. Normally not but there are some “tricks” Such Elan’s trait the character gain “wild talent”. As he choose to be Aegis “wild talent” become “psionic talent” ( described in Elan section). At this point he must spend 1 talent more for “Unlocked Talent” feat and gain ONE first lv psionic powers (described in chapter 5 Ultimate psionics)…. but if GM consider it appropriate “psionic talent”=”Unlocked Talent” (In campaigns where psionics is more common-place, it is recommended to remove the prerequisite of Wild Talent from Unlocked Talent and substitute the Unlocked Talent feat for Wild Talent to represent how the ability to manifest powers is common within the world.). It’s all right? And then spend one more talent to gain “Access Psionic Talent” and learn five 0 lv powers. Right?

Is there such a cryptographic algorithm?

Is there such a cryptographic algorithm that will encrypt any file with a password. But when decrypting, if the password is incorrect, the file will be decrypted, but instead of relevant data there will be “garbage”. It is important to note that I’m not talking about the ability to generate a file with garbage if the password is incorrect. I mean, that would be as if built into the algorithm itself. Is there something similar that I described? And if not, which way can I dig?

Is this set semi-decidable? A set of all that M is a TM halts on all input strings w such that w

A is a set of all < M > that M is a TM halt on all input strings w such that w <= q(M) where q(M) is the number of states in M.

Is A semi-decidable? Is a complement of A semidecidable?

I think A is semi-decidable. We can construct M*.

M1 = “On input < M > where M is TM

Simulate M on input with all of the string whose length is less than q(M). If all halts, accept”

The complement of A is not semi-decidable. But I’m not sure how to prove it